Java Creating Random Numbers with No Duplicates

Question

In this case, the MAX is only 5, so I could check the duplicates one by one, but how could I do this in a simpler way? For example, what if the MAX has a value of 20? Thanks.

int MAX = 5;

for (i = 1 , i <= MAX; i++)

{

        drawNum[1] = (int)(Math.random()*MAX)+1;


        while (drawNum[2] == drawNum[1])

        {
             drawNum[2] = (int)(Math.random()*MAX)+1;
        }

        while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )

        {
             drawNum[3] = (int)(Math.random()*MAX)+1;
        }

        while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )

        {
             drawNum[4] = (int)(Math.random()*MAX)+1;
        }

        while ((drawNum[5] == drawNum[1]) || (drawNum[5] == drawNum[2]) || (drawNum[5] == drawNum[3]) || (drawNum[5] == drawNum[4]) )

        {
             drawNum[5] = (int)(Math.random()*MAX)+1;
        }

}

Answer 1

The simplest way would be to create a list of the possible numbers (1..20 or whatever) and then shuffle them with Collections.shuffle. Then just take however many elements you want. This is great if your range is equal to the number of elements you need in the end (e.g. for shuffling a deck of cards).

That doesn't work so well if you want (say) 10 random elements in the range 1..10,000 - you'd end up doing a lot of work unnecessarily. At that point, it's probably better to keep a list of values you've generated so far, and just keep generating numbers in a loop until the next one isn't already present:

Random rng = new Random(); // Ideally just create one instance globally
List<Integer> generated = new ArrayList<Integer>();
for (int i = 0; i < numbersNeeded; i++)
{
    while(true)
    {
        Integer next = rng.nextInt(max) + 1;
        if (!generated.contains(next))
        {
            // Done for this iteration
            generated.add(next);
            break;
        }
    }
}

Yet another option is to always make progress, by reducing the range each time and compensating for existing values. So for example, suppose you wanted 3 values in the range 0..9. On the first iteration you'd generate any number in the range 0..9 - let's say you generate a 4.

On the second iteration you'd then generate a number in the range 0..8. If the generated number is less than 4, you'd keep it as is... otherwise you add one to it. That gets you a result range of 0..9 without 4. Suppose we get 7 that way.

On the third iteration you'd generate a number in the range 0..7. If the generated number is less than 4, you'd keep it as is. If it's 4 or 5, you'd add one. If it's 6 or 7, you'd add two. That way the result range is 0..9 without 4 or 6.

Answer 2

Here's how I'd do it

import java.util.ArrayList;
import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int size = 20;

        ArrayList<Integer> list = new ArrayList<Integer>(size);
        for(int i = 1; i <= size; i++) {
            list.add(i);
        }

        Random rand = new Random();
        while(list.size() > 0) {
            int index = rand.nextInt(list.size());
            System.out.println("Selected: "+list.remove(index));
        }
    }
}

As the esteemed Mr Skeet has pointed out:
If n is the number of randomly selected numbers you wish to choose and N is the total sample space of numbers available for selection:

1. If n << N, you should just store the numbers that you have picked and check a list to see if the number selected is in it.
2. If n ~= N, you should probably use my method, by populating a list containing the entire sample space and then removing numbers from it as you select them.

Answer 3

There is algorithm of card batch: you create ordered array of numbers (the "card batch") and in every iteration you select a number at random position from it (removing the selected number from the "card batch" of course).

Answer 4

You could use one of the classes implementing the Set interface (API), and then each number you generate, use Set.add() to insert it.

If the return value is false, you know the number has already been generated before.

Answer 5

Here is an efficient solution for fast creation of a randomized array. After randomization you can simply pick the n-th element e of the array, increment n and return e. This solution has O(1) for getting a random number and O(n) for initialization, but as a tradeoff requires a good amount of memory if n gets large enough.