快速随机选择算法

Question

给定一个真/假值数组,选择具有随机真值的索引的最有效算法是什么.

草图简单的算法是

a <- the array
c <- 0
for i in a:
    if a[i] is true: c++
e <- random number in (0, c-1)
j <- 0
for i in e:
    while j is false: j++
return j

任何人都可以提出更快的算法吗？即使最初不知道真元素的数量,也许有一种方法只能遍历列表一次？

Answer 1

使用"从无限列表中选择随机元素"算法.

保留当前选择的索引,以及您看到的真实值的数量.

当您看到真值时,递增计数,然后用当前索引替换您的选择,概率为P =(1 /计数).(所以你总是选择你找到的第一个......那么你可能会切换到第二个,概率为1/2,那么你可能会切换到第三个,概率为1/3等)

这只需要对列表进行一次扫描和恒定存储.(但它确实需要你计算出更多的随机数.)特别是,它不需要你缓冲列表或返回到开始 - 所以它可以在无界输入流上工作.

请参阅此答案,了解简单的"选择随机元素"算法的LINQ实现示例; 它只需要微小的调整.

Answer 2

使用指向true值的索引构建列表,并随机选择其中一个.需要O(n)进行列表遍历,并尝试使用随机数.