我有一个大小为 n 的输入流，我想生成大小为 k 的输出流，其中包含输入流的不同随机元素，而无需为样本选择的元素提供任何额外的内存。
我要使用的算法基本上如下：
for each element in input stream
if random()<k/n
decrement k
output element
if k = 0
halt
end if
end if
decrement n
end for
函数 random() 在随机分布上从 [0..1) 生成一个数字，我相信算法的操作原理很简单。
尽管此算法在选择最后一个元素时可以提前终止，但通常该算法仍约为 O(n)。 起初它似乎按预期工作(从输入流中输出大致均匀分布但仍然是随机的元素)，但我认为当 k 远小于 n 时，可能会有一种不均匀的趋势来选择后面的元素。 但是，我不确定这一点...所以我希望肯定知道一种或另一种方式。 我也想知道是否存在更快的算法。 显然，由于必须生成 k 个元素，因此算法不能比 O(k) 快。 对于 O(k) 解决方案，可以假设存在一个函数 skip(x)，它可以在 O(1) 时间内跳过输入流中的 x 个元素(但不能向后跳过)。 但是，我仍然希望保留不需要任何额外内存的要求。
如果是真实的流，则需要O(n)时间来扫描它。
你现有的算法很好。 (我以前弄错了。 你可以通过归纳法证明你在i尝试中没有选择第一个元素的概率是1 - i/n = (n-i)/n。 首先，通过检查i=0也是如此。 现在，如果您在i次尝试中没有选择它，那么下一次选择它的几率是1/(n-i). 然后在i+1次尝试时选择它的几率是((n-i)/n) * (1/(n-i)) = 1/n. 这意味着在前i+1次不选择它的几率是1 - i/n - 1/n = 1 - (i+i)/n. 这样就完成了归纳。 因此，在k第一次尝试中选择第一个元素的几率是没有选择它或1 - (n - k/n) = k/n的几率。
但是，如果您O(1)访问任何元素怎么办？ 请注意，选择k采取与选择n-k离开相同。 因此，在不失去一般性的情况下，我们可以假设k <= n/2. 这意味着我们可以使用这样的随机算法：
chosen = set()
count_chosen = 0
while count_chosen < k:
choice = random_element(stream)
if choice not in chosen:
chosen.add(choice)
count_chosen = count_chosen + 1
该集合将O(k)空间，并且由于每个随机选择对您来说是新的概率至少是0.5，因此预期的运行时间并不比2k选择差。