How to generate a random permutation in Java?
29,451
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]);
}
}
}
Related videos on Youtube
![Shankar Raju](https://i.stack.imgur.com/gozPU.jpg?s=256&g=1)
Author by
Shankar Raju
I am a Senior Software Engineer at Microsoft in Bellevue, WA. My opinions are my own and not part of my Employer. I have varied interests that include Music, playing Piano, Photography, Cooking and Technology.
Updated on July 09, 2022Comments
-
Shankar Raju almost 2 years
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.
-
Shankar Raju about 13 yearsThanks so much. But the api says it works in linear time. Is it possible for us to achieve this in less than O(n) complexity?
-
BlueRaja - Danny Pflughoeft about 13 years@Shankar: Yes
-
corsiKa about 13 years@Danny that's possible, but impractical.
-
Shankar Raju about 13 yearsMy bad! I changed it. But, I wanted the permutations to get generated randomly.
-
corsiKa over 12 years@metdos can you elaborate? I believe it's the knuth shuffle, and he kind of wrote the book on algorithms. Literally.
-
metdos over 12 yearsYes, you are right. I guess my problem is with the random generator. I created a list with length of 3, and I shuffled it 100000 times, and the results weren't satisfactory(is not close to uniform as much as I expect)