Problem
After reading this question I wanted to write a short example of how a list or sequence could be shuffled in .net. The result turned out to not be very short:
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
class Program
{
private static void Main()
{
var sequence = Enumerable.Range(1, 10);
Console.WriteLine(string.Join(", ", sequence.ProduceShuffle()));
var list = sequence.ToList();
Console.WriteLine(string.Join(", ", list));
list.Shuffle();
Console.WriteLine(string.Join(", ", list));
using (var random = new RNGCryptoServiceProvider())
{
Console.WriteLine(string.Join(", ", sequence.ProduceShuffleStrong(random)));
list.ShuffleStrong(random);
Console.WriteLine(string.Join(", ", list));
}
}
}
ShuffleExtensions.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
public static class ShuffleExtensions
{
public static IEnumerable<T> ProduceShuffle<T>(this IEnumerable<T> source)
{
Check.NotNull(source, "source");
return source.ProduceShuffle(new Random());
}
public static IEnumerable<T> ProduceShuffle<T>(this IEnumerable<T> source, Random random)
{
Check.NotNull(source, "source");
Check.NotNull(random, "random");
var values = source.ToList();
values.Shuffle(random);
return values;
}
public static void Shuffle<T>(this IList<T> source)
{
Check.NotNull(source, "source");
source.Shuffle(new Random());
}
public static void Shuffle<T>(this IList<T> source, Random random)
{
Check.NotNull(source, "source");
Check.NotNull(random, "random");
var length = source.Count;
for (var currentIndex = 0; currentIndex < length; currentIndex++)
{
var swapIndex = random.Next(currentIndex, length);
source.Swap(currentIndex, swapIndex);
}
}
public static IEnumerable<T> ProduceShuffleStrong<T>(this IEnumerable<T> source)
{
Check.NotNull(source, "source");
using (var random = new RNGCryptoServiceProvider())
{
return source.ProduceShuffleStrong(random);
}
}
public static IEnumerable<T> ProduceShuffleStrong<T>(this IEnumerable<T> source, RandomNumberGenerator random)
{
Check.NotNull(source, "source");
Check.NotNull(random, "random");
var values = source.ToList();
values.ShuffleStrong(random);
return values;
}
public static void ShuffleStrong<T>(this IList<T> source)
{
Check.NotNull(source, "source");
using (var random = new RNGCryptoServiceProvider())
{
source.ShuffleStrong(random);
}
}
public static void ShuffleStrong<T>(this IList<T> source, RandomNumberGenerator random)
{
Check.NotNull(source, "source");
Check.NotNull(random, "random");
var length = source.Count;
for (var currentIndex = 0; currentIndex < length; currentIndex++)
{
var swapIndex = random.Next(currentIndex, length);
source.Swap(currentIndex, swapIndex);
}
}
internal static void Swap<T>(this IList<T> source, int firstIndex, int secondIndex)
{
DebugCheck.InRange(firstIndex, "firstIndex", 0, source.Count);
DebugCheck.InRange(secondIndex, "secondIndex", 0, source.Count);
var temp = source[firstIndex];
source[firstIndex] = source[secondIndex];
source[secondIndex] = temp;
}
}
RandomNumberGeneratorExtensions.cs
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Security.Cryptography;
public static class RandomNumberGeneratorExtensions
{
public static int Next(this RandomNumberGenerator random, int maxValue)
{
Check.NotNull(random, "random");
Check.GreaterThan(maxValue, "maxValue", 0);
return random.Next(0, maxValue);
}
public static int Next(this RandomNumberGenerator random, int minValue, int maxValue)
{
Check.NotNull(random, "random");
Check.GreaterThanOrEqual(minValue, "minValue", 0);
Check.GreaterThan(maxValue, "maxValue", minValue, "minValue");
var range = maxValue - minValue;
var bytesForRange = GetBytesNeededForRange(range);
var rangeMax = GetMaxForInt32ByteCount(bytesForRange);
var biasThreshold = rangeMax - rangeMax % range;
var rawRange = new byte[bytesForRange];
while (true)
{
random.GetBytes(rawRange);
var valueInByteRange = RawBytesToInt(rawRange, bytesForRange);
if (valueInByteRange < biasThreshold)
{
var result = minValue + valueInByteRange % range;
DebugCheck.InRange(result, "result", minValue, maxValue);
return result;
}
}
}
private static int GetMaxForInt32ByteCount(int byteCount)
{
DebugCheck.InRangeInclusive(byteCount, "byteCount", 1, 4);
switch (byteCount)
{
case 1:
return 0x000000FF;
case 2:
return 0x0000FFFF;
case 3:
return 0x00FFFFFF;
case 4:
return 0x7FFFFFFF;
default:
throw new ArgumentOutOfRangeException(
"byteCount",
byteCount,
string.Format(
CultureInfo.InvariantCulture,
"byteCount was outside the range [1,4], actual {0}.",
byteCount)
);
}
}
private static int GetBytesNeededForRange(int range)
{
DebugCheck.GreaterThanOrEqual(range, "range", 0);
if (range > 0x00FFFFFF)
{
return 4;
}
if (range > 0x0000FFFF)
{
return 3;
}
if (range > 0x000000FF)
{
return 2;
}
return 1;
}
private static int RawBytesToInt(byte[] source, int byteCount)
{
DebugCheck.NotNull(source, "source");
DebugCheck.InRangeInclusive(byteCount, "byteCount", 1, 4);
int result;
switch (byteCount)
{
case 1:
result = source[0];
break;
case 2:
result = source[0] |
source[1] << 8;
break;
case 3:
result = source[0] |
source[1] << 8 |
source[2] << 16;
break;
case 4:
result = source[0] |
source[1] << 8 |
source[2] << 16 |
source[3] << 24;
result &= 0x7FFFFFFF;
break;
default:
throw new ArgumentOutOfRangeException(
"byteCount",
byteCount,
string.Format(
CultureInfo.InvariantCulture,
"byteCount was outside the range [1,4], actual {0}.",
byteCount)
);
}
DebugCheck.GreaterThanOrEqual(result, "result", 0);
return result;
}
}
The shuffle used is the Fisher–Yates shuffle. The strong shuffles uses the RandomNumberGenerator to produce a greater number of the possible permutations for collections with more than 12 elements.
I have not included the source for Check and DebugCheck. Check throws exceptions when the condition isn’t met and DebugCheck fails assertions. Methods in DebugCheck are also annotated with [Conditional("DEBUG")] so the
checks are omitted in non-Debug builds.
Is there anything that isn’t clear enough?
Am I constructing the random range correctly using RandomNumberGenerator?
Solution
You have a lot of unneeded calls to the various methods of the Check class which are repeated int the overloaded methods. These checks can mostly be ommitted shrinking the code.
Applying these suggestion would lead to ShuffleExtensions looking like so
public static class ShuffleExtensions
{
public static IEnumerable<T> ProduceShuffle<T>(this IEnumerable<T> source)
{
return source.ProduceShuffle(new Random());
}
public static IEnumerable<T> ProduceShuffle<T>(this IEnumerable<T> source, Random random)
{
// this check is needed, because we need to call `ToList()` on the `IEnumerable<T>`
Check.NotNull(source, "source");
var values = source.ToList();
values.Shuffle(random);
return values;
}
public static void Shuffle<T>(this IList<T> source)
{
source.Shuffle(new Random());
}
public static void Shuffle<T>(this IList<T> source, Random random)
{
Check.NotNull(source, "source");
Check.NotNull(random, "random");
var length = source.Count;
for (var currentIndex = 0; currentIndex < length; currentIndex++)
{
var swapIndex = random.Next(currentIndex, length);
source.Swap(currentIndex, swapIndex);
}
}
public static IEnumerable<T> ProduceShuffleStrong<T>(this IEnumerable<T> source)
{
using (var random = new RNGCryptoServiceProvider())
{
return source.ProduceShuffleStrong(random);
}
}
public static IEnumerable<T> ProduceShuffleStrong<T>(this IEnumerable<T> source, RandomNumberGenerator random)
{
// this check is needed, because we need to call `ToList()` on the `IEnumerable<T>`
Check.NotNull(source, "source");
var values = source.ToList();
values.ShuffleStrong(random);
return values;
}
public static void ShuffleStrong<T>(this IList<T> source)
{
using (var random = new RNGCryptoServiceProvider())
{
source.ShuffleStrong(random);
}
}
public static void ShuffleStrong<T>(this IList<T> source, RandomNumberGenerator random)
{
Check.NotNull(source, "source");
Check.NotNull(random, "random");
var length = source.Count;
for (var currentIndex = 0; currentIndex < length; currentIndex++)
{
var swapIndex = random.Next(currentIndex, length);
source.Swap(currentIndex, swapIndex);
}
}
internal static void Swap<T>(this IList<T> source, int firstIndex, int secondIndex)
{
DebugCheck.InRange(firstIndex, "firstIndex", 0, source.Count);
DebugCheck.InRange(secondIndex, "secondIndex", 0, source.Count);
var temp = source[firstIndex];
source[firstIndex] = source[secondIndex];
source[secondIndex] = temp;
}
}
this also applies to the Next() method in the RandomNumberGeneratorExtensions class like so
public static int Next(this RandomNumberGenerator random, int maxValue)
{
return random.Next(0, maxValue);
}
You have some magic numbers in your code which should be extracted to meaningful constants.
By omitting the DebugCheck calls at least in the RawBytesToInt() method and returning early in the switch you could reduce the numerbers of codelines which would add readability because the method would be shorter.
private static int RawBytesToInt(byte[] source, int byteCount)
{
switch (byteCount)
{
case 1:
return source[0];
case 2:
return source[0] |
source[1] << 8;
case 3:
return source[0] |
source[1] << 8 |
source[2] << 16;
case 4:
return (source[0] |
source[1] << 8 |
source[2] << 16 |
source[3] << 24)
& 0x7FFFFFFF;
default:
throw new ArgumentOutOfRangeException(
"byteCount",
byteCount,
string.Format(
CultureInfo.InvariantCulture,
"byteCount was outside the range [1,4], actual {0}.",
byteCount)
);
}
}