3

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.

jball
  • 24,791
  • 9
  • 70
  • 92
David Weng
  • 4,165
  • 12
  • 42
  • 51
  • Do the 10 have to be unique? Or is the possibility of repeats okay? – Jodaka Sep 13 '11 at 15:44
  • @Jokada yes, I need them to be unique. – David Weng Sep 13 '11 at 15:47
  • 2
    If you must ensure that it's unique, you can't ensure that it's truly random... – jball Sep 13 '11 at 15:47
  • 1
    What's your real world starting array length? – jball Sep 13 '11 at 15:48
  • @jball that sounds like a real cool quote, but a basic algorithm would be generating random sequences and throwing away the duplicate ones until you have the 10 unique ones. You still think this can't be considered random? – David Weng Sep 13 '11 at 16:16
  • At the very least, it allows for the prediction of what the algorithm won't produce. It certianly reduces the usefulness of the output for applications that demand the most randomness possible. Randomness is tricky too, in that (if I remember correctly - perhaps a more studied expert can weigh in with sources) pseudo-random sampling of pseudo-random numbers can actually lead to much more predictibility in the output. – jball Sep 13 '11 at 17:23

2 Answers2

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

:-)

C. K. Young
  • 219,335
  • 46
  • 382
  • 435
  • 1
    @Amir: This answer is too "enterprisey" to be able to submit as a homework entry. ;-) – C. K. Young Sep 13 '11 at 15:53
  • Of course the problem with algorithm is that it will always be the same 10 sequences! So if you want a different set of numbers on every run, you may want to do the recursion. – Amir Raminfar Sep 13 '11 at 15:56
  • 1
    @Amir someone tagged it as homework, but not the OP, and no one has mentioned homework apart from that, so while it may well be, it could also just be a question generated by a curious programmer :) – jball Sep 13 '11 at 15:57
  • 1
    @Amir: No, it won't. Java will auto-seed your RNG as necessary. :-P – C. K. Young Sep 13 '11 at 15:58
  • Yep. I stand corrected. Shuffle will be different on each run. That's good to know. – Amir Raminfar Sep 13 '11 at 16:00
3

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

barjak
  • 10,842
  • 3
  • 33
  • 47