c#的random shuffle

王朝c#·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航