When random is too consistent...

A while back I posted an extension method for shuffling Lists in C# using the Fisher Yates Shuffle. The algorithm is valid but my implementation relied on the default random number generator in .Net (System.Random) which is flawed since it generates a predictable sort of random.

Here's a correction that uses a more random sort of random from System.Security.Cryptography:

view plainprint?

1. public static void Shuffle<T>(this IList<T> list)  
2. {  
3.     var provider = new RNGCryptoServiceProvider();  
4.     int n = list.Count;  
5.     while (n > 1)  
6.     {  
7.         var box = new byte[1];  
8.         do provider.GetBytes(box);  
9.         while (!(box[0] < n * (Byte.MaxValue / n)));  
10.         var k = (box[0] % n);  
11.         n--;  
12.         var value = list[k];  
13.         list[k] = list[n];  
14.         list[n] = value;  
15.     }  
16. }  

public static void Shuffle<T>(this IList<T> list)
{
    var provider = new RNGCryptoServiceProvider();
    int n = list.Count;
    while (n > 1)
    {
        var box = new byte[1];
        do provider.GetBytes(box);
        while (!(box[0] < n * (Byte.MaxValue / n)));
        var k = (box[0] % n);
        n--;
        var value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

Here's a simple test you can run to demonstrate the difference in the algorithms:

view plainprint?

1. using System;  
2. using System.Collections.Generic;  
3. using System.Security.Cryptography;  
4.   
5. namespace AlphabetSoup  
6. {  
7.     class Program  
8.     {  
9.         static void Main()  
10.         {  
11.             var alphabet = GetAlphabet();  
12.             foreach (var c in alphabet)  
13.                 Console.Write(c);  
14.             Console.Write('\n');  
15.             Console.Write('\n');  
16.   
17.             Console.WriteLine("System.Random:");  
18.             for (int i = 0; i < 10; i++)  
19.             {  
20.                 alphabet = GetAlphabet();  
21.                 alphabet.QuickShuffle();  
22.                 foreach (var c in alphabet)  
23.                     Console.Write(c);  
24.                 Console.Write('\n');  
25.             }  
26.             Console.Write('\n');  
27.             Console.Write('\n');  
28.   
29.             Console.WriteLine("System.Security.Cryptography:");  
30.             for (int i = 0; i < 10; i++)  
31.             {  
32.                 alphabet = GetAlphabet();  
33.                 alphabet.Shuffle();  
34.                 foreach (var c in alphabet)  
35.                     Console.Write(c);  
36.                 Console.Write('\n');  
37.             }  
38.             Console.Write('\n');  
39.             Console.Write('\n');  
40.   
41.             Console.ReadKey();  
42.         }  
43.   
44.         static List<char> GetAlphabet()  
45.         {  
46.             var alphabet = new List<char>();  
47.             for (int c = 65; c < 91; c++)  
48.                 alphabet.Add((char)c);  
49.             return alphabet;  
50.         }  
51.     }  
52.     static class Ext  
53.     {  
54.         public static void Shuffle<T>(this IList<T> list)  
55.         {  
56.             var provider = new RNGCryptoServiceProvider();  
57.             int n = list.Count;  
58.             while (n > 1)  
59.             {  
60.                 var box = new byte[1];  
61.                 do provider.GetBytes(box);  
62.                 while (!(box[0] < n * (Byte.MaxValue / n)));  
63.                 var k = (box[0] % n);  
64.                 n--;  
65.                 var value = list[k];  
66.                 list[k] = list[n];  
67.                 list[n] = value;  
68.             }  
69.         }  
70.         public static void QuickShuffle<T>(this IList<T> list)  
71.         {  
72.             var rng = new Random();  
73.             var n = list.Count;  
74.             while (n > 1)  
75.             {  
76.                 n--;  
77.                 var k = rng.Next(n + 1);  
78.                 var value = list[k];  
79.                 list[k] = list[n];  
80.                 list[n] = value;  
81.             }  
82.         }  
83.     }  
84. }  

using System;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace AlphabetSoup
{
    class Program
    {
        static void Main()
        {
            var alphabet = GetAlphabet();
            foreach (var c in alphabet)
                Console.Write(c);
            Console.Write('\n');
            Console.Write('\n');

            Console.WriteLine("System.Random:");
            for (int i = 0; i < 10; i++)
            {
                alphabet = GetAlphabet();
                alphabet.QuickShuffle();
                foreach (var c in alphabet)
                    Console.Write(c);
                Console.Write('\n');
            }
            Console.Write('\n');
            Console.Write('\n');

            Console.WriteLine("System.Security.Cryptography:");
            for (int i = 0; i < 10; i++)
            {
                alphabet = GetAlphabet();
                alphabet.Shuffle();
                foreach (var c in alphabet)
                    Console.Write(c);
                Console.Write('\n');
            }
            Console.Write('\n');
            Console.Write('\n');

            Console.ReadKey();
        }

        static List<char> GetAlphabet()
        {
            var alphabet = new List<char>();
            for (int c = 65; c < 91; c++)
                alphabet.Add((char)c);
            return alphabet;
        }
    }
    static class Ext
    {
        public static void Shuffle<T>(this IList<T> list)
        {
            var provider = new RNGCryptoServiceProvider();
            int n = list.Count;
            while (n > 1)
            {
                var box = new byte[1];
                do provider.GetBytes(box);
                while (!(box[0] < n * (Byte.MaxValue / n)));
                var k = (box[0] % n);
                n--;
                var value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }
        public static void QuickShuffle<T>(this IList<T> list)
        {
            var rng = new Random();
            var n = list.Count;
            while (n > 1)
            {
                n--;
                var k = rng.Next(n + 1);
                var value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }
    }
}

Here's the output on my machine: