Shuffling an array

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]);
            }
        }
    }
}
Advertisements

About Moto

Engineer who likes coding
This entry was posted in Algorithm and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s