How to generate a random permutation in Java?

Question

What is the best way to generate a random permutation of n numbers?

For example, say I have a set of numbers 1, 2 and 3 (n = 3)

Set of all possible permutations: {123, 132, 213, 231, 312, 321}

Now, how do I generate:

• one of the elements of the above sets (randomly chosen)
• a whole permutation set as shown above

In other words, if I have an array of n elements, how do I shuffle them randomly? Please assist. Thanks.

Answer 1

java.util.Collections.shuffle(List); 

javadoc link for Collections.shuffle

List<Integer> list = new ArrayList<Integer>(); list.add(1); list.add(2); list.add(3); java.util.Collections.shuffle(list); 

It's worth noting that there are lots of algorithms you can use. Here is how it is implemented in the Sun JDK:

public static void shuffle(List<?> list, Random rnd) {     int size = list.size();     if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {         for (int i=size; i>1; i--)             swap(list, i-1, rnd.nextInt(i));     } else {         Object arr[] = list.toArray();          // Shuffle array         for (int i=size; i>1; i--)             swap(arr, i-1, rnd.nextInt(i));          // Dump array back into list         ListIterator it = list.listIterator();         for (int i=0; i<arr.length; i++) {             it.next();             it.set(arr[i]);         }     } }