algorithm - 如何在 n 位的非 2 次方元素上创建均匀分布？

Question

假设我可以生成随机数据字节，我如何使用它从 n 元素的数组中选择一个元素？

如果我有 256 个元素，我可以生成 1 字节的熵(8 位)，然后使用它来选择我的元素，只需将其转换为整数即可。

如果我有 2 个元素，我可以生成 1 个字节，丢弃 7 位并使用剩余的位来选择我的元素。

但是如果我有 3 个元素怎么办？ 1 位太少，2 位太多。我如何以等概率随机选择 3 个元素中的 1 个？

Answer 1

这里是对从随机位生成均匀随机整数的算法的综述。

• J. Lumbroso 的 Fast Dice Roller，发表于“Optimal Discrete Uniform Generation from Coin Flips, and Applications”，2013 年。另请参阅本答案末尾的实现。
• The Math Forum , 2004 年。另见“Bit Recycling for Scaling Random Number Generators”。
• D.勒米尔，“A Fast Alternative to the Modulo Reduction ”。
• M。奥尼尔，“Efficiently Generating a Number in a Range ”。

其中一些算法是“恒定时间”的，另一些是无偏的，还有一些算法在平均使用的随机位数方面是“最优的”。在这个答案的其余部分，我们将假设我们有一个“真正的”随机生成器，可以生成无偏且独立的随​​机位。

如需进一步讨论，请参阅我的以下回答:

• How to generate a random integer in the range [0,n] from a stream of random bits without wasting bits?