Menu
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:
In other words, if I have an array of n elements, how do I shuffle them randomly? Please assist. Thanks.
493
A simple algorithm to generate a permutation of n items uniformly at random without retries, known as the Fisher–Yates shuffle, is to start with any permutation (for example, the identity permutation), and then go through the positions 0 through n − 2 (we use a convention where the first element has index 0, and the ...
You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.
Approach: Create an array of N elements and initialize the elements as 1, 2, 3, 4, …, N then shuffle the array elements using Fisher-Yates shuffle Algorithm. Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates a random number in O(1) time.
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]); } } } If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
