CODEWITHSUNDEEP
javaalgorithmrandom
Tom
Tom

Reputation: 2254

Generate list of unique random numbers in constant time

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?

Upvotes: 3

Views: 1580

Answers (4)

Frank
Frank

Reputation: 15641

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.

Upvotes: 4

durron597
durron597

Reputation: 32323

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);
        }
    }
}

Upvotes: 0

saum22
saum22

Reputation: 882

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()

Upvotes: 0

damned
damned

Reputation: 945

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).

Upvotes: 0

Related Questions