Array Shuffle (Fisher Yates)
This page was last reviewed on Nov 17, 2022.
Dot Net Perls
Shuffle. We can develop a Java shuffling algorithm. In shuffling, we take a 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.
Detail 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.
Detail It is important to use nextInt instead a multiplication with Math.Random to avoid bias in the results.
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 send. 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); } } }
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.
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()); } }
BEFORE: [1, 2, 3, 4] AFTER 1: [3, 2, 4, 1] AFTER 2: [4, 1, 3, 2]
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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Nov 17, 2022 (simplify).
© 2007-2024 Sam Allen.