Generate list of unique random numbers in constant time

Question

I need 100 random numbers from the range 1 to 1,000,000. The numbers must be unique, no duplicates. It's similar to this question, but my range is too large to create an array from.

I need to generate these 100 random numbers many, many times, so generation needs to be as fast as possible, preferably O(1). What's the fastest way to do it?

But OP wants to generate `100`, not arbitrary number of random numbers. — Miserable Variable, Nov 02 '12 at 20:21
@MiserableVariable If you put it that way, it is **always** going to be O(1), no matter what you do. — Marko Topolnik, Nov 02 '12 at 20:22

score 4 · Accepted Answer · edited May 23 '17 at 10:26

4

I would use a HashSet and a Mersenne Twister.

code:

    MersenneTwisterFast ran = new MersenneTwisterFast();
    long time = System.nanoTime();
    Set set = new HashSet(100);
    while( set.size()<100) {
        set.add(ran.nextInt(1000000));
   }

System.out.println(System.nanoTime()-time+" : nano");
System.out.println(set.size());

The output was:

320000 : nano

100

Fast enough? and yes, this is O(1) as you always do 100 numbers.

Beware of the Birthday paradox, here you select 100 out of 1000000, thats ok but if you boost the 100 up, it will take longer and longer.

edited May 23 '17 at 10:26

Community

1
1

answered Nov 02 '12 at 20:12

Frank

16,476
7
38
51

Cool. Didn't know about the twister. – Jordan Kaye Nov 02 '12 at 20:24
The doc says it's only a third faster. In fact, `Random` is only a third slower than `MersenneTwisterFast`, which is even less difference. – Marko Topolnik Nov 02 '12 at 20:26
Javadocs I found for it say nextInt() "Returns an integer drawn uniformly from 0 to n-1". Does that mean it's guaranteed to never return a duplicate until you've called nextInt n times? – Marvo Nov 02 '12 at 20:27
1

I confirmed it using Caliper, really is over twice as fast as Random (Lion, JSE 7). – Marko Topolnik Nov 02 '12 at 20:39
Hm... I now extended my test and the story suddenly changed. The raw generator (`nextInt()`) is indeed twice as fast, but as soon as you use a bound (`nextInt(100)`) the difference melts to zero. – Marko Topolnik Nov 02 '12 at 20:49
@Frank: What happens if there are high collisions? It seems that `ran.nextInt()` may be called `150` times or even more. Is there any limit? – Yogendra Singh Nov 02 '12 at 20:55
Please look at the Birthday Paradox, the link is in my answer...but for this solution it means it will get slow. – Frank Nov 02 '12 at 20:55
@YogendraSingh do you have that with this code? i did put in a small if to detect collisions but with only 100 numbers i did get 0 after 100 test runs. – Frank Nov 02 '12 at 21:03
@Frank: I was more thinking theoretically than trying it. Since we are generating 100 numbers only, its low, but if we generate 100000 numbers, collision may be very high. Also if I do the same using random.nextInt(1000000), it should be same percentile of collisions. I thought of suggesting the same `Set` based approach using random.nextInt(n)), but I got hesitant just be thinking of the collisions. I haven't gauged the time difference though. – Yogendra Singh Nov 02 '12 at 21:13
@YogendraSingh that is what the Birthday paradox is all about. – Frank Nov 02 '12 at 21:14
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/18996/discussion-between-frank-and-yogendra-singh) – Frank Nov 02 '12 at 21:17
Working perfectly, really fast too. I'd never heard of MT before. Thanks. – Tom Nov 02 '12 at 21:35

score 0 · Answer 2 · answered Nov 02 '12 at 20:22

0

Divide your range in 100 parts and generate a random number from each sub-range. I think it'll work fine in your case.

Alternatively, generate random numbers and put them in a HashSet. when the size of the HashSet is 100, you break.

Though If you want to generate 100 random numbers, it'll always be O(1).

answered Nov 02 '12 at 20:22

damned

935
2
19
35

This equally spaces the numbers. Therefore they are not random! – durron597 Nov 02 '12 at 20:35

score 0 · Answer 3 · answered Nov 02 '12 at 20:22

Create a Random here.

 Random generator = new Random();

And create a timer class to execute the function every x seconds

 int d = 1000; //milliseconds 
 ActionListener t = new ActionListener() {
  public void actionPerformed(ActionEvent e) {
      //...Number genration task Here

  for (int idx = 1; idx <= 10; ++idx){
  int r = generator.nextInt(1000000);
  log("Generated : " + r);
  }
  }
  };
  new Timer(a,t).start()

score 0 · Answer 4 · answered Nov 02 '12 at 20:26

Disclaimer: this solution only works quickly when the amount of possible generated numbers greatly exceeds the amount of numbers you have to generate!

Edit: you can use this exact code with a Mersenne Twister also if you like

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;

public class MakeRand {
    private static final HashSet<Integer> theNumbers = new HashSet<Integer>();
    private static final Random myRandom = new Random();

    private static void addNumber() {
         int newNumber = -1;
         do {
            newNumber = myRandom.nextInt(1000000) + 1;
         } while(theNumbers.contains(newNumber));

         theNumbers.add(newNumber);
    }

    public static void populate(int howMany) {
        for (int i = 0; i < howMany; i++) {
            addNumber();
        }
    }

    public static void main(String args[]) {
        populate(100);

        Iterator<Integer> iter = theNumbers.iterator();
        while(iter.hasNext()) {
            Integer current = iter.next();
            System.out.println(current);
        }
    }
}

Generate list of unique random numbers in constant time

4 Answers4