In-Place swapping is a common way to shuffle an array. However, it’s easy to make an implementation mistake.

When the size of the array is N, there are N! permutations. The goal is, after the shuffling operation, each permutation shall happen in the probability of 1/N!.

The first (incorrect) example is swapping two random indexes.

for (int i = 0; i < array.Length; i++) { int swapIndex1 = rand.Next(0, array.Length); int swapIndex2 = rand.Next(0, array.Length); int temp = array[swapIndex1]; array[swapIndex1] = array[swapIndex2]; array[swapIndex2] = temp; }

This is incorrect because an array shuffled in an iteration can be back to the original state in another iteration. If you shuffle many times and plot the number of occurrences of each permutation, certain permutations happens much more often than other permutations as shown below.

How about calling random function just once per iteration? Nice try but be careful on the random range. A common mistake is that, for each iteration, the swapping target is selected from the whole array.

for (int i = 0; i < array.Length; i++) { int swapIndex = rand.Next(0, array.Length); int temp = array[i]; array[i] = array[swapIndex]; array[swapIndex] = temp; }

As this algorithm still allows the array state to go back to the original state, the probability of each permutation is not uniform. The graph plot is shown below.

The correct way is to get the random of the arrray[i .. N – 1] for each iteration i.

for (int i = 0; i < array.Length; i++) { # Take swap index [i ... N-1] int swapIndex = rand.Next(i, array.Length); int temp = array[i]; array[i] = array[swapIndex]; array[swapIndex] = temp; }

The graph is shown below. Each permutation occurs with roughly same probabilities.

The whole program used for the testing is shown below.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace PermutationTest { class Program { static int CalcPermIndex(int[] array) { int permIndex = 0; foreach (int v in array) { permIndex <<= 3; permIndex += v; } return permIndex; } static int Shuffle1(Random rand) { int[] array = { 0, 1, 2, 3, 4, 5 }; for (int i = 0; i < array.Length; i++) { int swapIndex1 = rand.Next(0, array.Length); int swapIndex2 = rand.Next(0, array.Length); int temp = array[swapIndex1]; array[swapIndex1] = array[swapIndex2]; array[swapIndex2] = temp; } return CalcPermIndex(array); } static int Shuffle2(Random rand) { int[] array = { 0, 1, 2, 3, 4, 5 }; for (int i = 0; i < array.Length; i++) { int swapIndex = rand.Next(0, array.Length); int temp = array[i]; array[i] = array[swapIndex]; array[swapIndex] = temp; } return CalcPermIndex(array); } static int Shuffle3(Random rand) { int[] array = { 0, 1, 2, 3, 4, 5}; for (int i = 0; i < array.Length; i++) { int swapIndex = rand.Next(i, array.Length); int temp = array[i]; array[i] = array[swapIndex]; array[swapIndex] = temp; } return CalcPermIndex(array); } static void Add(Dictionary<int, int[]> counter, int index, int pos) { if (counter.ContainsKey(index)) { counter[index][pos]++; } else { int[] array = new int[3]; array[pos] = 1; counter.Add(index, array); } } static void Main(string[] args) { Random rand = new Random(); Dictionary<int, int[]> counter = new Dictionary<int, int[]>(); for (int i = 0; i < 10000000; i++) { Add(counter, Shuffle1(rand), 0); Add(counter, Shuffle2(rand), 1); Add(counter, Shuffle3(rand), 2); } foreach (var i in counter.Values) { Console.WriteLine("{0} {1} {2}", i[0], i[1], i[2]); } } } }