c++ - 从 STL 容器中抽取 n 个随机元素(无替换)

Question

或多或少与this question相同但是如果要选择的容器尽可能通用(即只有一个 Forward Container 或什至可能只是一个简单的 Container )，则不应假设容器有一个 .size() 并走两次(一次)计算大小并再次获取结果集)是 Not Acceptable 。

我有一个解决方案，它比我想要的稍微复杂一点，依赖性也更多，所以我希望能有 3-5 行范围内的东西。

Answer 1

我假设“随机元素”是指均匀分布的元素。

由于您不知道序列的长度，也无法事先计算它，因此您必须逐步构建随机序列。因此，让我们这样做吧，希望我们使用的所有概率都能很好地相加，从而最终得到我们最初想要的结果。

我们将分两步进行。首先，决定抽取哪些序列号，然后我们可以根据需要为它们选择一个随机顺序(问题中并不清楚)。我会称你的 N 为“K”，因为这对我来说更容易。

首先我们创建一个K元素数组，用来存放K个绘制的元素。我们遍历序列的前 K 个元素并将它们复制到数组中。如果序列没有 K 个元素，我们说“不行”。

现在我们知道我们有来自 K 大小序列的 K 个随机元素。如果我们在序列的末尾，我们就完成了。如果不是，我们知道我们有一个 K+1 大小的序列。这里有两个选项，要么选择第 K+1 个项目，要么不选择。

第K+1项被选中的概率是多少？我发现计算第 K+1 个项目未被选中的概率更容易。从 K+1 中选择 K 个元素有 (K+1 over K) 种方法，如果 K+1 的元素没有出现，则只有 (K over K) 种方法选择 K 元素。所以 (K over K)/(K+1 over K) 是第 K+1 项未被选中的概率。

因此，选择一个介于 0 和 1 之间的随机数，如果它小于 1/(K+1)，则第 K+1 个元素不会出现在序列中。如果随机数大于该数，则第 K+1 个元素确实出现在序列中。从1到K中随机选择一个元素，替换为第K+1个元素。

现在我们移至下一项，即第 K+2 项。我们再次做同样的事情。第 K+2 个项目不出现在序列中的概率是 (K+1 over K)/(K+2 over K)。

这样做直到序列用完。然后你有一个从序列中随机选择的 K 元素的列表。

请注意，它们不是随机排序的(至少对于短序列而言不是)，因此您可能希望为此选择一个随机的 K 大小排列。

免责声明:概率是一个婊子，虽然这对我来说似乎是正确的，但我有可能错过了一些东西，最终结果不会平均分布。其他人很快就会说出来。