Generate unique random number between 0 and 1000

Question

Possible Duplicate:
Generating Unique Random Numbers in Java

How can I generate random number between 0 and 1000 and keep on passing unique random number that got generated between 0 and 1000 to a particular method. So for that I generated the number between 0 and 1000 and inserted unique random number between 0 and 1000 in List so that we can compare whether the random number we are generating is already present in the list or not. If it is present then generate it again. But somehow I believe the below code will fail sometimes.

public class Testing4 {
    private static List<Integer> randomNumber;
    private static Random r = new Random();
    private static int rand;
    private static int endRange = 1000;

    public static void main(String args[]) throws IOException {

        randomNumber = new ArrayList<Integer>();

        for (int i = 1; i<= endRange; i++) {
            rand = r.nextInt(endRange);

            if(randomNumber.contains(rand)) {
                rand = r.nextInt(endRange);
            } else {
                randomNumber.add(rand);
            }

        // Pass the unique random number between 0 and 1000 to this method      
                randomNumberMethod(rand);

        }
    }
}

Answer 1

You are essentially generating a List of the numbers from 0-1000 in a random order. You could achieve this more efficiently in the following way:

public class Testing4 {
    private static List<Integer> randomNumber;
    private static int endRange = 1000;

    public static void main(String args[]) throws IOException {

        randomNumber = new ArrayList<Integer>(endRange);

        for (int i = 0; i<= endRange; i++) {                
            randomNumber.add(i);
        }

        Collections.shuffle(randomNumber);

        for (int i = 0; i<= endRange; i++) {                
            // Pass the unique random number between 0 and 1000 to this method      
            randomNumberMethod(randomNumber.get(i));
        }
    }
}

Think about what will be happening by the time you get to 999 - you will have a 1 in 999 chance of 'guessing' the remaining available number each time round the loop.

Answer 2

To generate a unique list of numbers between 0 and 1000, do the following:

• create a list containing all the numbers from 0 to 1000
• shuffle the list using Collections.shuffle()
• take the first however many numbers you need from the list.

There are cases where a more complex algorithm is called for, but if the range of possible numbers and count of items you need to select are both in the order of 1000 you really may as well just take the first n numbers from a randomly shuffled list of all the possibilities.

If you do want to do something like you suggest, then:

• use a while loop as another poster has suggested
• use a Set, not a list, to store the already-chosen values.

However, this becomes inefficient as the number of items to select tends in magnitude towards the number of possible items (so e.g. if you're selecting 10 numbers out of a possible 1000, then it'll be OK; it you're selecting 900 out of a possible 1000 it will become inefficient as more and more numbers need to be rejected each time before finding one not previously chosen).

Answer 3

From code inspection, I cannot see anything in this method that will stop it from WORKING, it is just very inefficient.

For one thing, checking to see if the number is one that you have seen randomNumber.contains(rand) will take more and more time the more numbers you generate since each time you do it, you will have to compare it against every number in the list until either you find one that matches or you have tried every number in the list. A better way to do this is to use a HashSet instead of a list which should make every membership test take the same amount of time regardless of how many things you have put in it.

A second, and more significant optimization can be done by noting that you may be asking the wrong question. Are you trying to generate unique, random numbers or are you trying to generate every number between 1 and endRange in random order? If you are going to want every number (or even a non-trivial portion of them), it is going to be a great deal faster to just put every number from 1 to 1000 into a list and then shuffle them using Collections.shuffle. So your generation code is going to be:

java.util.List<Integer> nums = new java.util.ArrayList<Integer>(1001);
for (int i = 0; i <= 1000; i++)
{
   nums.add(new Integer(i));
}
java.util.Collections.shuffle(nums);

Answer 4

Your code will fail if 2 numbers that already exist in your ArrayList are generated consecutively. It will use the second number whether it is a duplicate or not. The if statement should be a while loop instead (to keep trying until it generates a unique one).

public class Testing4 {
    private static HashSet<Integer> randomNumber;
    private static Random r = new Random();
    private static int rand;
    private static int endRange = 1000;

    public static void main(String args[]) throws IOException {

        randomNumber = new HashSet<Integer>();

        for (int i = 1; i<= endRange; i++) {    
            do
            {
               rand = r.nextInt(endRange);
            }
            while(randomNumber.contains(rand));

            randomNumber.add(rand);

            // Pass the unique random number between 0 and 1000 to this method      
            randomNumberMethod(rand);

        }
    }
}

edit: as per the comments, you should use a do/while and a hashing data structure rather than an arraylist to speed up the duplicate lookups. The final edits are in the code above.