从一个集合中获取X个唯一的数字

Question

我在思考抓取唯一随机数的最优雅方式是什么？

目前，当我需要随机唯一数字时，我使用while循环来检查是否已经使用过该随机数，以确保它是唯一的。

代码如下：

int n = getRandomNumber % [Array Size];

for each ( Previously used n in list)
    Check if I've used n before, if I have...try again.

有很多方法可以解决这个线性O(n/2)问题，我只是想知道是否有一种优雅的方式来解决它。试图回想起MATH115离散数学课程中老师是否讲过与这个看似琐碎的问题有关的任何内容。

我现在想不出来，也许一旦我喝了咖啡，我的大脑就会因为咖啡而产生的高智商而理清思路。

- David van Dugteren

---

可能是重复的内容：从子集中获取五个唯一的随机数。 - Aryabhatta

Answer 1

如果你想从集合{1, ..., n}中不重复地随机抽取k个整数（以获取唯一的数字），那么你需要的是[n]的随机排列的前k个元素。生成这样的随机排列最优雅的方法是使用Knuth shuffle算法。请参见： http://en.wikipedia.org/wiki/Knuth_shuffle

- Aaron

---

这仅适用于足够小的 n。例如，如果 n >= 2^32-1，则不实用。 - codekaizen

@codekaizen：我从OP的帖子中推测出n是一个数组的大小，因此在这种情况下应该是可行的。 - President James K. Polk

@GregS：是的，在那种情况下，这是正确的。我读问题的方式是他想生成任意长度的序列。 - codekaizen

Answer 2

我该如何获取唯一的随机数呢？

1. 创建一个包含N个唯一元素的数组（例如范围在0到N-1之间的整数），将N作为arraySize和initialArraySize的值（arraySize = N; initialArraySize = N）。
2. 当需要随机数时：
   2.1 如果arraySize为零，则将arraySize设置为initialArraySize。
   2.2 生成index = getRandomNumber() % arraySize。
   2.3 获取result = array[index]。但是不要立即返回result。
   2.4 将array[index]与array[arraySize-1]交换位置。交换的意思是“交换” c = array[index]; array[index] = array[arraySize-1]; array[arraySize-1] = c。
   2.5 减少arraySize的值1。
   2.6 返回result。

这样就可以获得一系列不重复的随机数，直到唯一值用完为止。时间复杂度为O(1)。

- SigTerm

Answer 3

一个n位的最大周期线性移位反馈寄存器（LFSR）在重复一个内部状态之前将循环遍历其所有（2^n -1）个内部状态。当且仅当由一个选通序列加1形成的多项式mod 2是原始多项式时，LFSR才是最大周期LFSR。

因此，一个n位的最大周期LFSR将为您提供一系列（2^n - 1）个唯一的随机数，每个随机数都是n位长。

LFSR非常优雅。

- M.A. Hanin

---

当然，它将是伪随机的，并且完全预先确定的。使用算法生成的任何内容，而不涉及特殊类型的硬件，都将是PRNG。要使用TRNG，您必须利用被认为是随机的某种物理现象。 - M.A. Hanin

它也无法解决OP的问题，因为没有理由怀疑数组长度为2^n - 1。 - President James K. Polk

Answer 4

既然你要求唯一性，那么一个伪随机生成器就足够了，可以配置为不重复长达你需要的序列。例如，一个LCG：如果种子是uint32并且最初为0，则使用（1664525 * seed）+ 1013904223作为下一个种子，并取低位字作为您不重复的16位结果。

- joe snyder

---

我认为这并没有回答问题。虽然 MT 生成的周期不会重复（对于2^19937），但数字本身会重复，违反了提问者对数字唯一性的限制。 - codekaizen

你仍然将随机“序列”的周期与该序列中生成的数字的独特性混淆了。来自MT的序列中的数字一直重复出现。 - codekaizen

如何配置LCG以避免重复数字？ - codekaizen

如果您可以分解数组大小（如果您事先知道它很容易），那么这是可能的，但我怀疑这比@joe snyder所想象的要难得多。 - President James K. Polk