选择随机项目,但不知道项目总数

Question

我有一个案例,我需要选择一个随机项目,但我不知道项目的总数,我不想建立一个庞大的数组,然后选择一个项目.例如,这就是我现在所拥有的:

List<string> items;
while (true)
{
    string item = GetNextItem();
    if (item == null)
        break;
}
int index = random.GetNext(0, items.count);

正如你所看到的,我正在构建一个我真的不需要的巨大集合,我只需要一个介于0和项目数之间的随机数.这是我正在考虑做的事情,它有效,但我想知道是否有任何专家可以找到它的错误:

int index = -1;
int total;
string selectedItem;
while (true)
{
    string item = GetNextItem();
    if (item == null)
        break;

    ++total;
    int rnd = random.Next(0, total);
    if (rnd == total- 1)
    {
        index = total- 1;
        selectedItem = item;
    }
}

这给了我索引号和随机选择的项目.我在这背后的想法是,当有3个项目时,例如,我选择0到2之间的随机数(包括),如果它等于2,我使用新项目作为选定项目,如果不是忽略它.随着项目总数的增加,每个新项目被选中的机会也相应减少.

这种方法"好"吗？它是否像构建数组并随后选择项目一样"随机"？它是否尽可能快？请随机指导我完成无知.:)

Answer 1

你正在做的事情会起作用.

这是重述它可能使算法稍微清晰:

1. 选择第一项,有100%的可能性是当前选择
2. 如果有第二项,则有一半的机会它将取代当前的选择(如果你进行数学计算,那么它有50%的可能性将成为第一项,50%的可能性将成为第二项.项目)
3. 如果有第三个项目,则有1/3的机会它将替换当前的选择(再次,数学的每个项目的概率为1/3)
4. 如果有第四项,则有1/4的机会它将取代当前的选择
5. ......等......

请注意,您应该能够1/x通过说rand.Next(0,x) == 0(或任何其他整数0和x - 1包含它们之间的整数来计算机会;您不必费心使用total - 1.

这实际上是一个非常巧妙的方法; 最初我以为没有任何好办法做你所要求的!