C programming: Generate random n-combinations from given set?

Question

Say I have a pre-specified set S of m items. I would like to generate a random combination of n (unique) items taken from S.

Is there an easy way to implement this in C? I looked into rand() but it didn't seem to do what I want.

(EDIT to add more details)

The specific problem is to randomly choose n distinct elements from an array of size m. My first instinct is to do this:

idx_array = []

int idx = rand() % m

[if idx not in idx_array, add to idx_array. Otherwise repeat above line. Repeat until idx_array has size n]

But it doesn't look like this process is truly random. I'm still new to C and really just want to know if there's a built-in function for this purpose.

Any help appreciated.

Please show your research effort till time. Please read [Ask] page first. — Sourav Ghosh, Jul 01 '16 at 18:52
_There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs._ — Sourav Ghosh, Jul 01 '16 at 18:52
`But it doesn't look like this process is truly random. I'm still new to C and really just want to know if there's a built-in function for this purpose.` No, no computer can do true random number generation. It's pseudo-random. — SnakeDoc, Jul 01 '16 at 19:03

score 1 · Answer 1 · edited May 23 '17 at 10:33

1

Instead of generating a number from 1 to n with the possibility of duplicate, shuffle your array and then pick out of the first n elements:

#include <stdio.h>
#include <stdlib.h>

// Randomly shuffle a array
void shuffle (int * array, int n) {
  int i, j, tmp;

  for (i = n - 1; i > 0; i--) {
    j = arc4random_uniform(i + 1);
    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;
  }
}


int main (int argc, char const *argv[])
{
    const int m = 5;
    const int n = 3;

    int s[m] = {10, 20, 30, 40, 50};

    // Make a copy of s before shuffling it
    int t[m];
    for(size_t i = 0; i < m; i++)
    {
        t[i] = s[i];
    }
    shuffle(t, m);

    // Now, the first n elements of t is what you want
    for(size_t i = 0; i < n; i++)
    {
        printf("%d ", t[i]);
    }

    return 0;
}

Credit to Roland Illig for the Fisher-Yate shuffling function.

edited May 23 '17 at 10:33

Community

1
1

answered Jul 01 '16 at 19:03

Code Different

90,614
16
144
163

A classic performance hit... You shuffle a whole array just to get a sample... if the array is 2Gb of data and you're sampling 512 bytes, that's quite terrible. – Myst Jul 03 '16 at 04:51
The old adage: make it work first, then make it fast. The shuffle algorithm runs in `O(n)` which is very efficient. However, if you are dealing with array of that size, some optimization is obviously need. – Code Different Jul 03 '16 at 13:04
you're obviously right, and your shuffle approach is a classic solution for the problem. I think it's what they teach in schools around the world... But that is partly why I had to point the performance issues out. People forget to use their judgment when applying known solutions. Anyway, under the hope that you'll point out the performance caveat in the answer, I'll give this my vote :) – Myst Jul 03 '16 at 14:52

score -1 · Answer 2 · answered Jul 01 '16 at 19:03

-1

This is a sampling problem. There are a host of sampling algorithms but a straightforward algorithm which does the job pretty well is known as Reservoir Sampling. Refer geekforgeeks for more details on reservoir sampling.

answered Jul 01 '16 at 19:03

Swaroop

1,219
3
16
32

As good as the answer is, you essentially saying "there's an answer over there"... Could you post some content into the answer? – Myst Jul 02 '16 at 01:06

C programming: Generate random n-combinations from given set?

2 Answers2