Unique random number generation in an integer array [duplicate]

Question

Possible Duplicate:
Unique random numbers in O(1)?

How do I fill an integer array with unique values (no duplicates) in C?

int vektor[10];     for (i = 0; i < 10; i++) {     vektor[i] = rand() % 100 + 1; }  //No uniqueness here 

Answer 1

There are several ways to solve your problem, each has its own advantages and disadvantages.

First I'd like to note that you already got quite a few of responses that do the following: they generate a random number, then check somehow whether it was already used in the array, and if it was already used, they just generate another number until they find an unused one. This is a naive and, truth to be said, seriously flawed approach. The problem is with the cyclic trial-and-error nature of the number generation ("if already used, try again"). If the numeric range (say, [1..N]) is close to the length of the desired array (say, M), then towards the end the algorithm might spend a huge amount of time trying to find the next number. If the random number generator is even a little bit broken (say, never generates some number, or does it very rarely), then with N == M the algorithm is guaranteed to loop forever (or for a very long time). Generally this trial-and-error approach is a useless one, or a flawed one at best.

Another approach already presented here is generating a random permutation in an array of size N. The idea of random permutation is a promising one, but doing it on an array of size N (when M << N) will certainly generate more heat than light, speaking figuratively.

Good solutions to this problem can be found, for example, in Bentley's "Programming Pearls" (and some of them are taken from Knuth).

---

• 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. However, this algorithm doesn't require any extra memory in addition to your vektor array, as opposed to already offered variant with permutations (meaning that it takes O(M) memory, not O(N) as other permutation-based algorithms suggested here). The latter makes it a viable algorithm even for M << N cases.

The algorithm works as follows: iterate through all numbers from 1 to N and select the current number with probability rm / rn, where rm is how many numbers we still need to find, and rn is how many numbers we still need to iterate through. Here's a possible implementation for your case

#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 */ }  assert(im == M); 

After this cycle we get an array vektor filled with randomly chosen numbers in ascending order. The "ascending order" bit is what we don't need here. So, in order to "fix" that we just make a random permutation of elements of vektor and we are done. Note, that the this is a O(M) permutation requiring no extra memory. (I leave out the implementation of the permutation algorithm. Plenty of links was given here already.).

If you look carefully at the permutation-based algorithms proposed here that operate on an array of length N, you'll see that most of them are pretty much this very same Knuth algorithm, but re-formulated for M == N. In that case the above selection cycle will chose each and every number in [1..N] range with probabilty 1, effectively turning into initialization of an N-array with numbers 1 to N. Taking this into account, I think it becomes rather obvious that running this algorithm for M == N and then truncating the result (possibly discarding most of it) makes much less sense than just running this algorithm in its original form for the original value of M and getting the result right away, without any truncation.

---

• The Floyd algorithm (see here). This approach has the complexity of about O(M) (depends on the search structure used), so it is better suitable when M << N. This approach keeps track of already generated random numbers, so it requires extra memory. However, the beauty of it is that it does not make any of those abominable trial-and-error iterations, trying to find an unused random number. This algorithm is guaranteed to generate one unique random number after each call to the random number generator.

Here's a possible implementation for it for your case. (There are different ways to keep track of already used numbers. I'll just use an array of flags, assuming that N is not prohibitively large)

#define M 10 #define N 100      unsigned char is_used[N] = { 0 }; /* flags */ int in, im;  im = 0;  for (in = N - M; in < N && im < M; ++in) {   int r = rand() % (in + 1); /* generate a random number 'r' */    if (is_used[r])     /* we already have 'r' */     r = in; /* use 'in' instead of the generated number */    assert(!is_used[r]);   vektor[im++] = r + 1; /* +1 since your range begins from 1 */   is_used[r] = 1; }  assert(im == M); 

Why the above works is not immediately obvious. But it works. Exactly M numbers from [1..N] range will be picked with uniform distribution.

Note, that for large N you can use a search-based structure to store "already used" numbers, thus getting a nice O(M log M) algorithm with O(M) memory requirement.

(There's one thing about this algorithm though: while the resultant array will not be ordered, a certain "influence" of the original 1..N ordering will still be present in the result. For example, it is obvious that number N, if selected, can only be the very last member of the resultant array. If this "contamination" of the result by the unintended ordering is not acceptable, the resultant vektor array can be random-shuffled, just like in the Khuth algorithm).

---

Note the very critical point observed in the design of these two algoritms: they never loop, trying to find a new unused random number. Any algorithm that makes trial-and-error iterations with random numbers is flawed from practical point of view. Also, the memory consumption of these algorithms is tied to M, not to N

To the OP I would recommend the Floyd's algorithm, since in his application M seems to be considerably less than N and that it doesn't (or may not) require an extra pass for permutation. However, for such small values of N the difference might be negligible.

Answer 2

In your example (choose 10 unique random numbers between 1 and 100), you could create a list with the numbers 1 to 100, use the random number generator to shuffle the list, and then take the first 10 values from the list.

int list[100], vektor[10]; for (i = 0; i < 100; i++) {     list[i] = i; } for (i = 0; i < 100; i++) {     int j = i + rand() % (100 - i);     int temp = list[i];     list[i] = list[j];     list[j] = temp; } for (i = 0; i < 10; i++) {     vektor[i] = list[i]; } 

Based on cobbal's comment below, it is even better to just say:

for (i = 0; i < 10; i++) {     int j = i + rand() % (100 - i);     int temp = list[i];     list[i] = list[j];     list[j] = temp;      vektor[i] = list[i]; } 

Now it is O(N) to set up the list but O(M) to choose the random elements.