6
\$\begingroup\$

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?

Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ @Snowbody - deleted my answer. Thanks for the heads up. Would be interested to see you elaborate on "Unless the range is exactly a power of two, it will prefer some numbers at the expense of other". \$\endgroup\$
    – RobH
    Jul 2, 2015 at 15:23

1 Answer 1

Reset to default
1
\$\begingroup\$

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

}
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ I don't agree on most of the removed precondition checks. I would rather do nothing and fail early than doing something and then failing, even if this requires checking the same thing multiple times. The assertions are there to guide in any refactoring, I don't personally think a few lines saved are better than an explicit pre- or post condition. \$\endgroup\$
    – Johnbot
    Jul 7, 2015 at 10:53
  • \$\begingroup\$ "The assertions are there to guide in any refactoring..." that what unit tests are for. \$\endgroup\$
    – Heslacher
    Jul 7, 2015 at 11:37
  • \$\begingroup\$ But you only unit test the public API. \$\endgroup\$
    – Johnbot
    Jul 7, 2015 at 11:39
  • \$\begingroup\$ Can you clarify which precondition checks your are refering to ? \$\endgroup\$
    – Heslacher
    Jul 7, 2015 at 11:40
  • \$\begingroup\$ All the DebugCheck's except the one in Next and the ones like in ProduceShuffle where you removed the Check.NotNull(random, "random"); so ToList would be called even if random was null. \$\endgroup\$
    – Johnbot
    Jul 7, 2015 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.