洗牌以覆盖所有可能的排列

Question

.NET框架中的Random对象以一个32位整数作为种子。这意味着任何使用Random对象的洗牌算法最多只能生成40亿种可能的洗牌方法（假设洗牌是根据随机序列确定的，我无法想象为什么不是这样）。这意味着一旦集合超过13个元素，就可以保证洗牌将不覆盖所有可能的排列方式。随着集合大小远离这个大小，洗牌所覆盖的可能排列子集变得越来越微不足道。

40亿是一个（主观上）很大的数字，但如果您正在生成一个集合的多个“随机”排列，则重复出现的几率比应该高得多（特别是当考虑到生日悖论/鸽笼原理时）。

有没有简单的方法可以解决这个问题，而不需要我实现自己的随机数生成器？

- Patrick M

---

如果你的应用/项目合适的话，可以考虑使用Random.org的在线API进行随机生成；这只是我的个人意见。 - Lexicon

如果您正在使用此功能进行游戏等目的，您可能应该切换到加密安全的随机数生成器。 - Damien_The_Unbeliever

分而治之：int digitNum = 10; long l = 0; Random r = new Random(DateTime.Now.Millisecond); for (int i = 0; i < digitNum; i++) l += r.Next(0, 9) * (long)Math.Pow((double)10, (double)i); - Johnny

请注意，DateTime.Millisecond 只会根据系统的不同每隔几毫秒才会改变。 - Matthew Watson

http://ericlippert.com/2013/05/06/producing-permutations-part-seven/。想想看，你应该从http://ericlippert.com/2013/04/15/producing-permutations-part-one/开始阅读整个系列。在其中，他展示了如何将随机数转换为排列。 - Jim Mischel

Answer 1

我不建议您创建自己的随机数生成器（RNG）。它们背后的理论非常可靠。如果您需要更“随机”的东西，则需要使用加密安全的RNG。要使用.NET框架提供的默认生成器：

using System.Security.Cryptography;

var generator = RandomNumberGenerator.Create();

您可以使用此方法获取一些随机字节，然后将其转换为int或其他值类型。

- Ananke

Answer 2

你可以使用其中一个免费提供的Mersenne Twister的C#端口。MT19937具有19937位状态空间，虽然你可以选择使用单个int进行种子处理，但如果你拥有适当的熵源以供输入，完整状态的种植也是可行的。

- pjs