如果我不知道集合的大小,我可以从集合中选择一个随机元素吗？

Question

我正在编写一些JavaScript代码,如果项目符合某些要求,应该从画布中选择一个随机项.有不同种类的项目(圆形,三角形,正方形等),并且每种类型的项目数量通常不同.这些项目按层次排列(因此正方形可以包含几个圆圈,圆圈可以包含其他圆圈等等 - 它们都可以嵌套).

现在,我选择随机项目的(原始)方法是:

1. 递归遍历画布并构建一个(可能是巨大的!)项目列表
2. 洗牌清单
3. 从前面迭代混洗列表,直到找到满足一些额外要求的项目.

这个问题是它不能很好地扩展.我经常遇到内存问题,因为递归深度太高或者项目总列表变得太大.

我正在考虑重写这段代码,以便在遍历画布时考虑选择元素 - 但如果我不知道总共有多少元素,我不知道如何"随机"选择一个元素.

有没有人知道如何解决这个问题？

Answer 1

你可以在没有先创建列表的情况下这样做(抱歉我的C伪代码)

int index = 0;
foreach (element)
{
    if (element matches criteria)
    {
        index++;
        int rand = random value in [1 index] range
        if (1 == rand)
        {
            chosen = element;
        }
    }
}

数学计算出来了,假设你有一个列表,其中3个元素符合标准,第一个元素将被选择的概率是:

1 * (1 - 1 / 2) * (1 - 1 / 3) = 1 * (1 / 2) * (2 / 3) = 1 / 3

选择第二个的概率是:

(1 / 2) * (1 - 1 / 3) = (1 / 2) * (2 / 3) = 1 / 3

最后是第三个元素

1 / 3

哪个是正确的答案.

Answer 2

从max_r = -1和开始rand_node = null.通过树迭代.对于符合条件的每个节点:

r = random()
if r > max_r:
  rand_node = node
  max_r = r

最后rand_node将是一个随机选择的节点,只需要一次迭代.