# Randomly Permute Elements in a List

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++)

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);
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#?

-
For what it's worth, there's a library which can do this for you. –  Bobson Feb 14 '13 at 14:28

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;
}


## 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);

-
Your code has been applied to my production whose link was given in my question. Thank you. –  kiss my armpit Sep 10 '12 at 2:57
Is it better to declare the swapIndex before the loop for? –  kiss my armpit Sep 10 '12 at 3:34
@GarbageCollector no, things like that are optimized by the compiler. Declare variables as close to their usage as possible (in the innermost scope) to increase readability and prevent side-effects. –  codesparkle Sep 10 '12 at 7:43
Confirmed. Thanks. –  kiss my armpit Sep 10 '12 at 7:45
I must say I was impressed by the quality of your given answer. I was about to provide an answer until I saw yours and nothing more valuable could be added. Only thing I would do is extract the code for the shuffling and put it into an extension-method. –  Abbas Feb 13 '13 at 12:19

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.

-
No need to worry about "passing the complete list" as this is not the case — only a reference is copied. Your source of randomness is fundamentally flawed, however: DateTime.Now.Millisecond is always a value between 0 and 999, a horribly small range for a seed. Use the default constructor (implemented with DateTime.Now.Ticks) or, better yet, follow Jon Skeet's advice and pass in an instance of Random as a parameter to your extension method. –  codesparkle Feb 13 '13 at 17:27
Additionally, if Shuffle is called often in rapid succession, it may yield the same resulting lists as the instances of Random will have the same seed. –  codesparkle Feb 13 '13 at 17:29
Thanks for your comment, I didn't know that yet! ;) –  Abbas Feb 14 '13 at 8:29

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.

-

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;

}

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)
{
}

}


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.

-
I agree with the accepted answer, but downvoters should leave a reason. OP's solution is quadratic O( n^2 ) at best, since List<>.remove() requires copying elements in the array. My solution is O( n log(n) ), a good improvement over OPs and was the first solution offered. Accepted solution is O( n ), which is an improvement over mine. –  Xantix Sep 10 '12 at 4:21
If the down-voter wanted to leave a reason he would have done so already; complaining about it is silly given the context. This has been argued many/many times on meta and it always comes back to it should always be optional. meta.stackexchange.com/q/119570/138817 –  Loki Astari Sep 10 '12 at 16:14
PS. I also tempted to down vote you as you are not answering the question based on the sites parameters. You are supposed to review and comment the code provided not provide a solution (this is not SO). Your answer provides very little useful feedback to the OP in this context. –  Loki Astari Sep 10 '12 at 16:17
Thanks for the feedback. I am used to SO, and just starting with CR. –  Xantix Sep 10 '12 at 22:25