假设我有一个长度为N的数字链表。 N非常大，我不知道N的确切值。

我如何最有效地编写一个从列表中返回k个完全随机数的函数？

解决方案

回答

我建议：首先找到k个随机数。对它们进行排序。然后遍历链表和随机数一次。

如果我们不知道链表的长度(如何？)，则可以将第一个k捕获到数组中，然后对于节点r，在[0，r)中生成一个随机数，如果小于大于k，请替换数组的第r个项目。 (不完全相信这不会产生偏见...)

除此之外："如果我是你，我不会从这里开始。"我们确定链接列表适合问题吗？是否没有更好的数据结构，例如好的旧式平面数组列表。

回答

好吧，我们确实至少需要知道N在运行时是什么，即使这涉及对列表进行额外的传递以对其进行计数。最简单的算法是从N中选择一个随机数并删除该项目，重复k次。或者，如果允许返回重复编号，请不要删除该项目。

除非我们有一个非常大的N，并且对性能的要求非常严格，否则此算法的运行复杂度为O(N * k)，应该可以接受。

编辑：没关系，汤姆·豪顿(Tom Hawtin)的方法更好。首先选择随机数，然后遍历列表一次。我认为理论上的复杂度相同，但预期的运行时间要好得多。

回答

你为什么不能做这样的事情

List GetKRandomFromList(List input, int k)
  List ret = new List();
  for(i=0;i<k;i++)
    ret.Add(input[Math.Rand(0,input.Length)]);
  return ret;

我确定意思不是那么简单，我们可以进一步指定吗？

回答

这称为水库采样问题。一种简单的解决方案是为列表中的每个元素分配一个随机数，如我们所见，然后按照该随机数的顺序保留前k个(或者后k个)元素。

回答

如果我们不知道列表的长度，则必须遍历整个列表以确保随机选择。我在这种情况下使用的方法是Tom Hawtin(54070)描述的方法。在遍历列表时，我们会保留形成随机选择的k个元素。 (最初，我们只添加遇到的第一个k元素。)然后，以概率'k / i'，用列表的第i个元素(即我们所在的元素)替换我们选择的随机元素。 ，当时)。

很容易证明这给出了一个随机选择。看到" m"个元素(" m> k")后，我们发现列表中的每个前" m"个元素都是我们随机选择的一部分，概率为" k / m"。这最初是微不足道的。然后，对于每个元素" m + 1"，将其以概率" k /(m + 1)"放入选择(替换随机元素)中。现在，我们需要证明所有其他元素也具有被选择的概率" k /(m + 1)"。我们有概率为" k / m (k /(m + 1)(1-1 / k)+(1-k /(m + 1)))"(即元素在列表中的概率乘以它仍然存在的概率)。使用微积分，我们可以直接证明这等于k /(m + 1)。