Wednesday, July 16, 2008

Generating unique random numbers

How to generate unique random numbers from 0 to N-1 given a random number generator which generates a random number between 0 to M-1 for a given M?


void generateRandomNumbers(int x[], int n)
{
int i, j, t;
for(i=0; i < n; i++)
x[i] = i;
for(i=0; i < n; i++) {
j = random(n-i);
t = x[i];
x[i] = x[j];
x[j] = t;
}
}

The complexity of this solution is O(n).

4 comments:

  1. i think this also works

    void main()
    {
    int n,i;
    printf("enter n value");
    scanf("%d",&n);
    randomize();
    for(i=0;i<=n;i++)
    printf("%d",random(i));
    }

    ReplyDelete
  2. This does not generate unique random numbers between 1 to n.

    This always gives first element as 0. In the first x elements, you will never see any number more than x. This is not random.

    ReplyDelete
  3. ya agree wid u ,
    it wud be random(n)

    ReplyDelete
  4. If it is random(n), then it is not guaranteed to be unique. If you call random(n) twice, you may get the same no both times. But, we need unique random numbers.

    ReplyDelete