Unique random numbers in an integer array in the C

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

I think this will do it (I've not tried to build it, so syntax errors are left to fix as an exercise for the reader). There might be more elegant ways, but this is the brute force solution:

int vektor[10];    
int random;
int uniqueflag;
int i, j

for(i = 0; i < 10; i++) {
     do {
        /* Assume things are unique... we'll reset this flag if not. */
        uniqueflag = 1;
        random = rand() % 100+ 1;
        /* This loop checks for uniqueness */
        for (j = 0; j < i && uniqueflag == 1; j++) {
           if (vektor[j] == random) {
              uniqueflag = 0;
           }
        }
     } while (uniqueflag != 1);
     vektor[i] = random;
}

Answer 2

One way would be to check if the array already contains the new random number, and if it does, make a new one and try again.

This opens up for the (random ;) ) possibility that you'd never get a number which is not in the array. Therefore you should count how many times you check if the number is already in the array, and if the count exceeds MAX_DUPLICATE_COUNT, throw an exception or so :) (EDIT, saw you're in C. Forget the exceptionpart :) Return an error code instead :P )

Answer 3

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.

Answer 4

Here is an O(M) average-time method.

Method: If M <= N/2, use procedure S(M,N) (below) to generate result array R, and return R. If M > N/2, use procedure S(N-M,N) to generate R, then compute X = {1..M}\R [the complement of R in {1..M}], shuffle X with Fisher-Yates shuffle [in time O(M)], and return X.

In the M > N/2 case, where O(M) == O(N), there are several fast ways to compute the complement. In the code shown below, for brevity I have only included an example of procedure S(M,N) coded inline in main(). Fisher-Yates shuffle is O(M) and is illustrated in main answer to related question #196017. Other previous related questions: #158716 and #54059.

The reason that S(M,N) takes O(M) time instead of O(N) time when M < N/2 is that, as described in Coupon-collector's problem the expectation E(t_k) is kH_k, from which E(t_{k/2}) = k(H_k - H_{k/2}) or about k*(ln(k)-ln(k/2)+O(1)) = k*(ln(k/(k/2))+O(1)) = k*(ln(2)+O(1)) = O(k).

Procedure S(k,N): [The body of this procedure is the dozen lines after the comment "Gen M distinct random numbers" in the code below.] Allocate and initialize three M+1-element integer arrays H, L, and V to all -1 values. For i=0 to M-1: Put a random value v into V[i] and into the sentinel node V[-1]. Get one of M list heads from H[v%M] and follow that list until finding a match to v. If the match is at V[-1] then v is a new value; so update list head H[v%M] and list link L[i]. If the match is not at V[-1], get and test another v, etc.

Each "follow the list" step has expected cost O(1) because at each step except the last, average list length is less than 1. (At end of processing, the M lists contain M elements, so average length gradually rises to exactly 1.)

 // randomMofN - jiw 8 Nov 2011     
 // Re: https://stackoverflow.com/questions/1608181/
 #include <stdlib.h>
 #include <stdio.h>
 int main(int argc, char *argv[]) {
   int h, i, j, tM, M, N, par=0, *H, *L, *V, cxc=0;
   // Get M and N values
   ++par; M = 42;  if (argc > par) M = atoi(argv[par]);
   ++par; N = 137; if (argc > par) N = atoi(argv[par]);
   tM = 3*M+3;
   H = malloc(tM*sizeof(int));
   printf ("M = %d,  N = %d  %s\n", M, N, H?"":"\nmem error");
   if (!H) exit(13);
   for (i=0; i<tM; ++i)           // Init arrays to -1's
     H[i] = -1;
   L = H+M;  V = L+M;

   // Gen M distinct random numbers
   for (i=0; i<M; ++i) {
     do {
       ++cxc;                     // complexity counter
       V[-1] = V[i] = random()%N;
       h = V[i]%M;                // h = list-head index
       j = H[h];
       while (V[j] != V[i])
         j = L[j];
     } while (j>=0);
     L[i] = H[h];
     H[h] = i;
   }

   // Print results
   for (j=i=0; i<M; ++i) {
     j += printf ("%4d ", V[i]);
     if (j>66) j = printf ("\n");
   }
   printf ("\ncxc %d\n", cxc);
   return 0;
 }

Answer 5

Generate first and second digits separately. Shuffle them later if required. (syntax from memory)

int vektor[10];
int i = 0;

while(i < 10) {
  int j = rand() % 10;
  if (vektor[j] == 0) { vektor[j] = rand() % 10 + j * 10; i ++;}
}

However, the numbers will be nearly apart by n, 0 < n < 10.

Or else, you need to keep the numbers sorted (O(n log n)), so that newly generated can be quickly checked for presence (O(log n)).

Answer 6

i like the Floyd algorithm.

but we can take all the random number from 0 to M (an not to in) :

#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() % (N + 1); /* generate a random number 'r' */

  while (is_used[r])
  {
     /* we already have 'r' */
     r = rand() % (N + 1);
  }
  vektor[im++] = r + 1; /* +1 since your range begins from 1 */
  is_used[r] = 1;
}

assert(im == M);