0

Shuffling of arrays/lists sounds like a trivial task, but in reality it’s full of subtle traps. Here we show how to implement Fisher-Yates Shuffle Algorithm in Java.

Shuffling traps

There are some things to be aware when implementing/choosing shuffling algorithm:

  • Use good Pseudo-Random Number Generator, one that uniformly distributes random numbers;
  • Shuffling algorithm should produce each permutation with equal probability; That’s why correct range for random numbers is important. Taking wrong range may produce biased results, which is illustrated nicely at Data Genetics (see the Monte Carlo simulation at the bottom).

Fisher-Yates shuffle

The most known and optimal shuffling algorithm is Fisher-Yates shuffle. The algorithm is very easy to implement and produces unbiased results. It has been modernized by Durstenfeld and popularized by Donald Knuth in The Art of Computer Programming TV series. The Durstenfeld’s implementation of the Fisher-Yates shuffling algorithm is extremely simple and boils down to just a few lines of code. What’s important, it runs in linear time and works in place: 

// T[] data, Random rand
for (int i = data.length-1; i > 0; --i) {
    swap(data, i, rand.nextInt(i+1));
}

How Durstenfeld shuffling works

  1. Go from the end of the array/list (you can process in the oposite direction by just changing directions in all the steps).
  2. Pick random number between 0 and the current position (both inclusive).
  3. Exchange the current item with the random one.

Complete Java example

package com.farenda.tutorials.algorithms.shuffling;

import java.util.Arrays;
import java.util.Random;

public class RandomSort {

    public static void main(String[] args) {
        String[] data = "HelloShuffleWorld!".split("");

        System.out.println("Before shuffle: "
            + Arrays.toString(data));

        shuffle(data, new Random());

        System.out.println("Shuffled: "
            + Arrays.toString(data));
    }

    private static <T> void shuffle(T[] data, Random rand) {
        for (int i = data.length-1; i > 0; --i) {
            swap(data, i, rand.nextInt(i+1));
        }
    }

    private static <T> void swap(T[] data, int i, int j) {
        T tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

If you happen to know why there is no swap() method in java.util.Arrays, please let me know in the comments! This is just incredible.

The above code produces shuffled output: 

Before shuffle: [H, e, l, l, o, S, h, u, f, f, l, e, W, o, r, l, d, !]
Shuffled: [r, W, l, l, h, o, f, d, e, l, e, f, H, o, !, u, S, l]

Now you are ready to implement card shuffling in you games. :-)

References:

Share with the World!