CODEWITHSUNDEEP
javarandom
David Weng
David Weng

Reputation: 4235

Generating random unique sequences in Java

I have an array of numbers, let's say for example it's

[1, 3, 5, 7, 9]

It is possible to generate 5! that is 120 unique sequences of these numbers. For example

1 3 5 7 9
5 1 3 9 7
7 3 9 5 1
1 7 9 5 3
... and so forth

I need to generate 10 of these sequences randomly, with no duplicates. Any suggestions would be much appreciated.

Upvotes: 3

Views: 7181

Answers (2)

barjak
barjak

Reputation: 11270

What you want is to generate n random permutations of a given array. There is a simple algorithm for generating one random permutation, which is well explained on wikipedia. You still have to check for uniqueness, though.

In Java :

Random rand = new Random();

int[] generateRandomPermutation(int n) {
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        int d = rand.nextInt(i+1);
        res[i] = res[d];
        res[d] = i;
    }
    return res;
}

Another solution is to use a permutation numbering scheme (presented here), and generate the corresponding permutation of n random distinct integers (from 0 to s!-1, where s is the size of the array).

Upvotes: 3

C. K. Young
C. K. Young

Reputation: 223003

List<Integer> template = Arrays.asList(1, 3, 5, 7, 9);
Set<List<Integer>> seen = new HashSet<List<Integer>>();
for (int i = 0; i < 10; ++i) {
    List<Integer> items = new ArrayList<Integer>(template);
    do {
        Collections.shuffle(items);
    } while (!seen.add(items));
    System.out.println(items);
}

:-)

Upvotes: 4

Related Questions