Monday, June 29, 2009

Shuffling a LinkedList (c#)

Since I could not google a sample shuffle function for the LinkedList, here it goes one:

public static void Shuffle(LinkedList list)
{
Random rand = new Random();

for (LinkedListNode n = list.First; n != null; n = n.Next)
{
T v = n.Value;
if (rand.Next(0, 2) == 1)
{
n.Value = list.Last.Value;
list.Last.Value = v;
}
else
{
n.Value = list.First.Value;
list.First.Value = v;
}
}
}

[TestMethod]
public void ShufleTest()
{
LinkedList<string> list = new LinkedList<string>();
list.AddLast("a");
list.AddLast("b");
list.AddLast("c");
list.AddLast("d");
list.AddLast("e");
Shuffle(list);
foreach(string s in list) {
Console.WriteLine(s);
}
}

1 comment:

  1. The outcome of this shuffle is not a uniform distribution. Even worse a lot of end combinations can't be reached. You can see this if you look at the permutations and the number of possible outcomes your algorithm an provide (n! > 2^n). For larger n "randomess" gets worse.

    ReplyDelete