Randomly Permute Elements in a List

Question

I want to randomly permute a finite list in the most effective and efficient way in C#. My attempt is as follows.

/*===================================*
 * Compile it to produce Shuffle.exe *
 * ==================================*/
using System;
using System.Collections.Generic;
using System.IO;

namespace Shuffle
{
    class Program
    {
        static void Main(string[] args)
        {
            int Columns = int.Parse(args[0]);
            int Rows = int.Parse(args[1]);
            int Seed = int.Parse(args[2]);
            string OutputFilename = args[3];


            List<string> OrderedList = new List<string>();
            for (int x = 0; x < Columns; x++)
                for (int y = 0; y < Rows; y++)
                    OrderedList.Add(string.Format("{{{0},{1}}}", x, y));

            Random rnd = new Random(Seed);
            List<string> ShuffledList = new List<string>();

            for (int i = 0; i < Columns * Rows; i++)
            {
                int x = rnd.Next(OrderedList.Count);
                ShuffledList.Add(OrderedList[x]);
                OrderedList.RemoveAt(x);
            }

            using (StreamWriter sw = new StreamWriter(OutputFilename))
            {
                foreach (string s in ShuffledList)
                    sw.WriteLine(s);
            }

        }
    }
}

This program will be used in my production. Could you review whether or not my code is already the most efficient and effective in C#?

Answer 1

Don't waste time on micro-optimizations. Use the simplest possible techniques that are known to perform well. In your specific case, it means replacing your multiple lists with one single array and using the standard fisher-yates-shuffle.

Naming conventions

In good C# code, local variables are camelCase beginning with a lower case letter. I renamed most of your variables to better express intent.

---

Generating the strings

You'll get a performance increase of about 30%-40% by using an array instead of a list (not much to be gained here).

Don't bother with string concatenation instead of string.Format, there is hardly any measurable difference in speed, but a huge difference in readability and maintainability.

string[] elements = new string[columns * rows];
for (int column = 0; column < columns; column++)
    for (int row = 0; row < rows; row++)
        elements[columns * row + row] = string.Format("{{{0},{1}}}", column, row);  

---

Shuffling them

Whenever you remove from a list, all the remaining elements have to be shifted to fill the gap. Use your array instead and use the fisher-yates-shuffle; don't attempt inventing your own.

for (int i = elements.Length - 1; i > 0; i--)
{
    int swapIndex = random.Next(i + 1);
    string tmp = elements[i];
    elements[i] = elements[swapIndex];
    elements[swapIndex] = tmp;
}

This runs about 160 times as fast as your shuffling implementation.

---

Don't reinvent the wheel

When saving the results to disk, use File.WriteAllLines which does exactly what you were doing with the StreamWriter - in a single line.

File.WriteAllLines(outputFilename, elements);

---

Complete code ^{(argument parsing omitted)}

Once you've realized that a few milliseconds more or less don't matter, it would be good to split this up into several methods that each do exactly one thing. I'll leave that as an exercise to you.

string[] elements = new string[columns * rows];
for (int column = 0; column < columns; column++)
    for (int row = 0; row < rows; row++)
        elements[column*rows + row] = string.Format("{{{0},{1}}}", column, row);

Random random = new Random(seed);
for (int i = elements.Length - 1; i > 0; i--)
{
    int swapIndex = random.Next(i + 1);
    string tmp = elements[i];
    elements[i] = elements[swapIndex];
    elements[swapIndex] = tmp;
}

File.WriteAllLines(outputFilename, elements);

Answer 2

This is an answer in addition to the answer of "codesparkle". His answer brings the best answer to this question but in the comments we talked further. The code below is my result of this:

//This is an extension method using the Fisher-Yates-shuffle
public static void Shuffle<T>(this IList<T> list)
{
    Random random = new Random(DateTime.Now.Millisecond);

    for (int i = list.Count - 1; i >= 0; i--)
    {
        int r = random.Next(i + 1);
        T value = list[r];
        list[r] = list[i];
        list[i] = value;
    }
}

The code of swapping could also be done within a while-loop, but after a little research I found that a for-loop is more performant when putting the 'list.Count' inside the statement. This makes sure the max value is already known and the bounds-check doesn't have to be done during the iteration. (Source)

Following code achieves the same as above, only here the swap is also extracted to an extension method. This extension method makes it easy to swap two elements from any IList.

public static void Shuffle<T>(this IList<T> list)
{
    Random random = new Random(DateTime.Now.Millisecond);

    for (int i = list.Count - 1; i >= 0; i--)
    {
        int r = random.Next(i + 1);
        list.Swap(r, i);
    }
}

public static void Swap<T>(this IList<T> list, int index1, int index2)
{
    T value = list[index1];
    list[index1] = list[index2];
    list[index2] = value;
}

Altough I'm not completely sure if calling Swap() in a loop is as performant as the first way of randomizing, as you're passing the complete list to the Swap-method every time. Either way, it is a nice extension method to swap elements in a list.

Answer 3

If performance is not really critical I would probably prefer the following solution to randomize elements in any enumerable:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list)
{
    Random random = new Random();
    return list.OrderBy(arg => random.Next(int.MaxValue));
}

In a quick test this method was about 3 times slower than shuffling in-place using random element swapping (@Abbas solution).

Note that strictly speaking it is not equivalent to other solutions since it creates a new enumerable rather than shuffling elements within existing list.

Answer 4

Here's what I came up with, it needs to be cleaned up and documented some more, but here's the gist.

Since the random accesses into Lists<> turn out to be slow (especially removing items), we can get rid of that.

So, make an array of numbers.

Assign those numbers randomly to the elements in the List if they haven't been used before.

Now you have a Dictionary where the string is the original elements, and the int is the random position.

Now sort the Dictionary by value (the random location).

Now return it as a List again.

    private static void randomizeList3(List<string> OrderedList, 
                                       List<string> ShuffledList, Random rnd)
    {
        int count = OrderedList.Count;
        int twoCount = 2 * count;

        bool[] usedNums = new bool[twoCount];

        Dictionary<String, int> dicto = new Dictionary<string, int>(count);

        int nextPos;

        foreach (string s in OrderedList)
        {
            nextPos = rnd.Next(twoCount);
            while (usedNums[nextPos] == true)
            {
                nextPos = rnd.Next(twoCount);
            }
            usedNums[nextPos] = true;

            dicto.Add(s, nextPos);
        }

        List<KeyValuePair<string, int>> myList = dicto.ToList();

        myList.Sort(
            delegate(KeyValuePair<string, int> firstPair,
            KeyValuePair<string, int> nextPair)
            {
                return firstPair.Value.CompareTo(nextPair.Value);
            }
        );

        foreach (KeyValuePair<string, int> p in myList)
        {
            ShuffledList.Add(p.Key);
        }

    }

I use a usedNums array which is twice as big, so that the chance of randomly choosing an already used element is only 50%.

Anyway, after timing on an instance of 200 cols, 200 rows:

Original Approach takes 12,805 milliseconds
   randomizeList3 takes 214 milliseconds

on a grid 2000 by 2000,

   randomizeList3 takes 4,425 milliseconds.

I'm sure this could be improved.