BAM! Blog

Quick and Dirty Shuffle: Best Practices for Programming Randomization

Written by Ethan Brown | Oct 31, 2016 6:00:00 PM

 

If that headline doesn’t generate some interesting traffic, I don’t know what will….

I hate to disappoint you, but this post is not about dirty dancing.

Have you ever needed to shuffle (randomize) a collection of items? Most people’s first take is something like this:

[code lang=”csharp”]
var things = new[]{ “One Fish”, “Two Fish”, “Red Fish”, “Blue Fish” };
var r = new Random();
var randomThings = new[]{
things[r.Next(things.Count())],
things[r.Next(things.Count())],
things[r.Next(things.Count())],
};
[/code]

The problem with this code is that there will be duplicates…that is, you could get “One Fish” twice, or even three times. Sometimes you want to actually shuffle your collection…like a deck of cards.

The quick and dirty way to do that is to associate each item in your collection with a random number…then sort by the random number. Then you have a shuffled collection!

Wouldn’t it be even nicer if IEnumerable<T> supported such a method right out of the box? Well, thanks to the magic of extension and LINQ methods, you can make it appear that way:

[code lang=”csharp”]
public static class EnumerableExtensions {
public static IEnumerable<T> Shuffle<T>( this IEnumerable<T> l, Random r=null ) {
if( r == null ) r = new Random();
var d = l.ToDictionary( x => r.NextDouble(), x => x );
return d.OrderBy( x => x.Key ).Select( x => x.Value );
}
}
[/code]

Now whenever you need to shuffle something, it’s easy:

[code lang=”csharp”]
var things = new[]{ “One Fish”, “Two Fish”, “Red Fish”, “Blue Fish” };
var randomThings = things.Shuffle();
[/code]

Isn’t life grand?

One note on my implementation of the Shuffle() extension method. You’ll note that you can pass it an instance of Random; this is an important consideration to keep in mind whenever you’re writing methods that involve entropy. For testing purposes, it’s often desirable to repeat pseudorandom sequences. Without the ability to pass an instance of Random into the method, that would be impossible. For example:

[code lang=”csharp”]
var things = new[]{ “One Fish”, “Two Fish”, “Red Fish”, “Blue Fish” };
var r = new Random(93028);
var randomThings = things.Shuffle(r);
[/code]

Now randomThings will be shuffled…but repeatably so. Every time you execute this code, you’ll get exactly the same order, which can be key for testing or simulation purposes.

Happy coding!

 

Originally posted April 25th, 2013.