Java Shuffle Arrays (Fisher Yates)

Implement the Fisher-Yates shuffle to randomly sort an array. Use Collections.shuffle.

Shuffle. An array is nicely sorted. In shuffling, we take that sorted array and mess it all up. We rearrange elements randomly, like a deck of cards.

In Fisher-Yates shuffle, a fast shuffling algorithm, we loop over an array. We swap each element with a random element past the iteration point.

In this program, we implement the shuffling algorithm. We call the Math.random() method, which returns a random double between 0 and 1. We use this to select a random index.Math Random

Swap: Then we swap the randomly selected "forward" element with the current element.

Result: The input array (in this code, an int array) is now randomly sorted. Like a deck of cards, it is shuffled.

NextInt: It is important to use nextInt instead a multiplication with Math.Random to avoid bias in the results.

Java program that implements Fisher-Yates shuffle public class Program { static void shuffle(int[] array) { int n = array.length; Random random = new Random(); // Loop over array. for (int i = 0; i < array.length; i++) { // Get a random index of the array past the current index. // ... The argument is an exclusive bound. // It will not go past the array's end. int randomValue = i + random.nextInt(n - i); // Swap the random element with the present element. int randomElement = array[randomValue]; array[randomValue] = array[i]; array[i] = randomElement; } } public static void main(String[] args) { int[] values = { 100, 200, 10, 20, 30, 1, 2, 3 }; // Shuffle integer array. shuffle(values); // Display elements in array. for (int value : values) { System.out.println(value); } } } Output 10 100 1 200 3 20 2 30

Collections.shuffle. The Collections class in java.util.Collections provides a shuffle() method. This receives an argument like an ArrayList.

Here: We call Collections.shuffle multiple times on an ArrayList. Its ordering changes after each call.

Java program that uses Collections.shuffle import java.util.ArrayList; import java.util.Collections; public class Program { public static void main(String[] args) { // Create an ArrayList of 4 elements. ArrayList<Integer> array = new ArrayList<>(); array.add(1); array.add(2); array.add(3); array.add(4); System.out.println("BEFORE: " + array.toString()); // Shuffle elements. Collections.shuffle(array); System.out.println("AFTER 1: " + array.toString()); // Shuffle elements again. Collections.shuffle(array); System.out.println("AFTER 2: " + array.toString()); } } Output BEFORE: [1, 2, 3, 4] AFTER 1: [3, 2, 4, 1] AFTER 2: [4, 1, 3, 2]

Concerns. Implementing the Fisher-Yates shuffle is prone to error. The Wikipedia page on Fisher-Yates has provided incorrect Java and Python implementations.

Quote: Fisher-Yates shuffling is similar to randomly picking numbered tickets out of a hat without replacement until there are none left.

Fisher-Yates shuffle: Wikipedia

With this code, we use an index selection that is provided in Sedgewick's Introduction to Programming in Java. Robert Sedgewick is a renowned computer science professor at Princeton.Arrays: Princeton.edu

National Institute of Standards. This organization recommends the index selection shown here (and featured on the above-linked page).Fisher-Yates shuffle: nist.gov

Correction: Thanks to Alan Evans for correcting a bias caused by Math.Random. It is better to use nextInt for the shuffle.

Alternative. Here is another strategy: we can generate an array of random numbers that is the same length as our array. Then we sort both arrays together.

And: This will randomly sort (or shuffle) the array, provided our random number generator is random enough.

However: This is not fast. But if your program only shuffles occasionally, this may be fast enough.

Correctness is key. With Fisher-Yates shuffling, we have a fast and useful algorithm. But implementing the indexes (and the index section part) is prone to small errors in logic.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java Shuffle Arrays (Fisher Yates)

Related Links:

.Net

Java

Related Links