algorithm - 在不知道项目总数的情况下选择一个随机项目

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. 如果有第二个项目，有 1/2 的机会替换当前选择(如果你算一下，那么它有 50% 的机会成为第一个项目，50% 的机会成为第二个项目)
3. 如果还有第三项，有一个1/3 的机会它会取代当前选择(同样，数学上每个项目的概率为 1/3)
4. 如果有第四项，有1/4的几率它将取代当前选择
5. ...等等...

请注意，您应该能够通过说 rand.Next(0,x) == 0(或 之间的任何其他整数)来计算 1/x 机会code>0 和 x - 1 包括在内；您不必费心使用 total - 1。

这实际上是一种非常巧妙的方法；最初我认为没有任何好的方法可以完成您的要求!