In this post, we will discuss how to shuffle or randomize a List in Java using Fisher–Yates shuffle algorithm and shuffle() method provided by the Collections class.
Randomize a List using Fisher–Yates Shuffle Algorithm:
Fisher–Yates shuffle algorithm can be used for generating random permutations of a finite sequence where every permutation is equally likely. Since it is an in-place algorithm and takes linear time, it is recommended approach for shuffling an array or list in any programming language.
Below is an implementation of Fisher–Yates shuffle algorithm which shuffles the list from highest index to lowest:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; class ListUtil { // Generic function to randomize a list in Java using Fisher–Yates shuffle public static<T> void shuffle(List<T> list) { Random random = new Random(); // start from end of the list for (int i = list.size() - 1; i >= 1; i--) { // get a random index j such that 0 <= j <= i int j = random.nextInt(i + 1); // swap element at i'th position in the list with element at // randomly generated index j T obj = list.get(i); list.set(i, list.get(j)); list.set(j, obj); } } public static void main (String[] args) { List<Integer> list = new ArrayList( Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)); shuffle(list); System.out.println(list); } } |
Below is an equivalent version of above algorithm which shuffles the list from lowest index to highest:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; class ListUtil { // Generic function to randomize a list in Java using Fisher–Yates shuffle public static<T> void shuffle(List<T> list) { Random random = new Random(); int n = list.size(); // start from beginning of the list for (int i = 0; i < n - 1; i++) { // get a random index j such that i <= j <= n int j = i + random.nextInt(n - i); // swap element at i'th position in the list with element at // randomly generated index j T obj = list.get(i); list.set(i, list.get(j)); list.set(j, obj); } } public static void main (String[] args) { List<Integer> list = new ArrayList( Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)); shuffle(list); System.out.println(list); } } |
Randomize a list using Collections.shuffle()
The simplest way to randomize a list is to use Collections.shuffle() method as shown below:
|
1 2 3 4 5 |
// Generic function to randomize a list using Collections.shuffle() in Java public static<T> void shuffle(List<T> list) { Collections.shuffle(list); } |
It is worth noting that internally Collections.shuffle() also uses Fisher–Yates shuffle algorithm by creating an intermediary array from the list, shuffling the array and converting the array back into the list. Below implementation in Java is pretty much similar to JDK implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.*; class ListUtil { // Generic function to randomize a list in Java public static void shuffle(List<?> list) { Random random = new Random(); // convert the list into an array Object arr[] = list.toArray(); // Shuffle array using reverse for loop for (int i = list.size(); i > 1; i--) { int j = random.nextInt(i); // generate a random index Object tmp = arr[i - 1]; arr[i - 1] = arr[j]; arr[j] = tmp; } // Dump array back into list ListIterator it = list.listIterator(); for (int i = 0; i < arr.length; i++) { it.next(); it.set(arr[i]); } } public static void main (String[] args) { List<Integer> list = new ArrayList( Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)); shuffle(list); System.out.println(list); } } |
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply