Generate Random Numbers in Array [duplicate]

Possible Duplicate:
Unique random numbers in O(1)?

I am new in Java. I want to generate a set of random numbers from a given set and the numbers must also not repeat. For example, the possible numbers are [0,1,2,3], I want to get three random unique numbers stored in an Array. Ex. [0,2,1], [2,3,1], [0,3,2] etc.

Solution 1:

You need a Fisher-Yates shuffle.

This is a very efficient "select n from m" solution that gives you a subset of your values with zero possibility of duplicates (and no unnecessary up-front sorting). Pseudo-code to do this follows:

dim n[N]                  // gives n[0] through n[N-1]
for each i in 0..N-1:
    n[i] = i              // initialise them to their indexes

nsize = N                 // starting pool size
do N times:
    i = rnd(nsize)        // give a number between 0 and nsize-1
    print n[i]
    nsize = nsize - 1     // these two lines effectively remove the used number
    n[i] = n[nsize]

By simply selecting a random number from the pool (based on the current pool size), replacing it with the top number from that pool, then reducing the size of the pool, you get a shuffle without having to worry about a large number of swaps up front.

This is important if the number is high in that it doesn't introduce an unnecessary startup delay.

For example, examine the following bench-check, choosing 10-from-10:

<------ n[] ------>
0 1 2 3 4 5 6 7 8 9  nsize  rnd(nsize)  output
-------------------  -----  ----------  ------
0 1 2 3 4 5 6 7 8 9     10           4       4
0 1 2 3 9 5 6 7 8        9           7       7
0 1 2 3 9 5 6 8          8           2       2
0 1 8 3 9 5 6            7           6       6
0 1 8 3 9 5              6           0       0
5 1 8 3 9                5           2       8
5 1 9 3                  4           1       1
5 3 9                    3           0       5
9 3                      2           1       3
9                        1           0       9

You can see the pool reducing as you go and, because you're always replacing the used one with an unused one, you'll never have a repeat.

Here's a little Java program that shows this in action:

import java.util.Random;

public class testprog {
    private int[] pool;           // The pool of numbers.
    private int size;             // The current "size".
    private Random rnd;           // A random number generator.

    // Constructor: just initilise the pool.

    public testprog (int sz) {
        pool = new int[sz];
        size = sz;
        rnd = new Random();
        for (int i = 0; i < size; i++) pool[i] = i;
    }

    // Get next random number in pool (or -1 if exhausted).

    public int next() {
        if (size < 1) return -1;
        int idx = rnd.nextInt(size--);
        int rval = pool[idx];
        pool[idx] = pool[size];
        return rval;
    }

    // Test program for the pool.

    public static void main(String[] args) {
        testprog tp = new testprog (10);
        for (int i = 0; i < 11; i++) System.out.println (tp.next());
    }
}

The output is (for one particular run):

3
5
1
0
6
4
9
2
8
7
-1

The -1 is there just to show you what happens when you exhaust the list. Since you've explicitly stated you don't want duplicates, it returns a sentinel value. You could also choose other options such as throwing an exception or just restarting the pool.