Generating array of unique random numbers

Question

I am writing a function that is supposed to populate an array with random numbers from 0 to n (where n is passed argument to the function), but all numbers in array should be unique. I basically need to shuffle the array of numbers from 0 to n

I found this answer here: Unique random numbers in an integer array in the C programming language

And used the "Knuth Algorithm" suggested by user:

void generate_random_array(int count)
{
  int in, im;

  im = 0;
  srand(time(NULL));

  for (in = 0; in < count && im < count; ++in) {
    int rn = count - in;
    int rm = count - im;
    if (rand() % rn < rm) random_array[im++] = in; 
  }
}

However this function does not generate random numbers for me at all, its simply creates an array of numbers from 0 to count. How can I generate the actual random sequence of unique numbers.

Answer 1

A C implementation example of the algoritm is as follows in the answer you quoted:

#define M 10
#define N 100

int in, im;

im = 0;

for (in = 0; in < N && im < M; ++in) {
  int rn = N - in;
  int rm = M - im;
  if (rand() % rn < rm)    
    /* Take it */
    vektor[im++] = in + 1; /* +1 since your range begins from 1 */
}

The Knuth algorithm. This is a very simple algorithm with a complexity of O(N) (i.e. the numeric range), meaning that it is most usable when M is close to N.

but you set M == N which is not close, but equal

So the initial values of rn and rm are the same. so which cannot make the algorithm work properly because:

whatever % rn < rm

is always true, like 345436 % 22 < 22 would since a % b < b, always.

So test is always true, integer is stored each time, so in and im increase by 1 each time, and so on.

I basically need to shuffle the array of numbers from 0 to n

This algorithm isn't what you need: it doesn't shuffle an array at all, it yields ordered random numbers (so, unique) by picking one from the increasing value from time to time. Constraining the values like you're doing forces the algorithm to issue all the values of the range.

You'll have better luck with Shuffle array in C

Answer 2

I basically need to shuffle the array of numbers from 0 to n

Well then why not do that? The Knuth algorithm is for selecting a random subset of the overall range specified, which it emits in ascending order. It is which subset that is random, not the order of the elements, but there is only one subset that contains all the elements. In any case, if you want them in random order then you still need to shuffle the result of Knuth's algorithm, which leaves you exactly where you started.