c#的random shuffle

2006马上就要过去了,blog也长草了。贴上一点代码,意思一下


      前段时间在C#里需要用到random shuffle功能,一时没找到合适的代码,就按自己的理解写了一段,所得到结果也能满足自己的需要。值得注意的一点是随机数生成器的选择。直接以Random做为随机数生成器因为时钟精度问题,在一个小的时间段内会得到同样的伪随机数序列,你shuffle后会得到同一个结果。.net提供了RNGCryptoServiceProvider可以避免这种情况,下面是几种用法的示例


 1     /// <summary>
 2     /// RandomShuffle
 3     /// WuErPing 2006/12/07
 4     /// </summary>
 5     public sealed class RandomShuffle
 6     {
 7         private RandomShuffle() { }
 8
 9         // pseudo-random number generator, using a time-dependent default seed value.
10         static public List<int> Shuffle(int size)
11         {
12             List<int> list = new List<int>(size);
13             for (int i = 0; i < size; ++i)
14             {
15                 list.Insert(i, i);
16             }
17             System.Random random = new Random();
18             for (int i = 0; i < list.Count; ++i)
19             {
20                 int var = random.Next(0, list.Count);
21                 int temp = list[i];
22                 list[i] = list[var];
23                 list[var] = temp;
24             }
25
26             return list;
27         }
28
29         // using a RNGCryptoServiceProvider().GetHashCode() seed value
30         static public List<int> ShuffleEx(int size)
31         {
32             List<int> list = new List<int>(size);
33             for (int i = 0; i < size; ++i)
34             {
35                 list.Insert(i, i);
36             }
37             System.Random random = new Random(new RNGCryptoServiceProvider().GetHashCode());
38             for (int i = 0; i < list.Count; ++i)
39             {
40                 int var = random.Next(0, list.Count);
41                 int temp = list[i];
42                 list[i] = list[var];
43                 list[var] = temp;
44             }
45
46             return list;
47         }
48
49         // Cryptographic random number generators create cryptographically strong random values
50         static public List<int> ShufflePro(int size)
51         {
52             List<int> list = new List<int>(size);
53             for (int i = 0; i < size; ++i)
54             {
55                 list.Insert(i, i);
56             }
57             byte[] randomBytes = new Byte[4];
58             RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
59             for (int i = 0; i < list.Count; ++i)
60             {
61                 rng.GetNonZeroBytes(randomBytes);
62                 int randomSeed = (randomBytes[0] << 24) | (randomBytes[1] << 16) | (randomBytes[2] << 8) | randomBytes[3];
63                 int var = randomSeed % list.Count;
64                 //var = System.Math.Abs(var);
65                 if (var < 0) var *= -1;
66                 int temp = list[i];
67                 list[i] = list[var];
68                 list[var] = temp;
69             }
70             return list;
71         }
72     }
注:如果要深究random shuffle算法,可以看标准C++的random_shuffle的实现。根据SGI的文档http://www.sgi.com/tech/stl/random_shuffle.html,算法来自
[1] This algorithm is described in section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981). Knuth credits Moses and Oakford (1963) and Durstenfeld (1964).


附:vc8的random_shuffle的实现


 1         // TEMPLATE FUNCTION random_shuffle
 2 template<class _RanIt,
 3     class _Diff> inline
 4     void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *)
 5     {    // shuffle [_First, _Last)
 6     _DEBUG_RANGE(_First, _Last);
 7     const int _RANDOM_BITS = 15;    // minimum random bits from rand()
 8     const int _RANDOM_MAX = (1U << _RANDOM_BITS) – 1;
 9
10     _RanIt _Next = _First;
11     for (unsigned long _Index = 2; ++_Next != _Last; ++_Index)
12         {    // assume unsigned long big enough for _Diff count
13         unsigned long _Rm = _RANDOM_MAX;
14         unsigned long _Rn = ::rand() & _RANDOM_MAX;
15         for (; _Rm < _Index && _Rm != ~0UL;
16             _Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)
17             _Rn = _Rn << _RANDOM_BITS
18                 | (::rand() & _RANDOM_MAX);    // build random value
19
20         std::iter_swap(_Next, _First + _Diff(_Rn % _Index));    // swap a pair
21         }
22     }
23
http://www.cnblogs.com/WuErPIng/archive/2006/12/31/609224.html