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).
Posted by at

4 comments:

  1. AnonymousMay 19, 2009 at 12:35 AM

    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. tnsatishMay 19, 2009 at 8:07 AM

    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. AnonymousMay 20, 2009 at 12:38 AM

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

    ReplyDelete
  4. tnsatishMay 20, 2009 at 9:09 AM

    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

Subscribe to: Post Comments (Atom)