或多或少与这个问题相同，但是要从中选择的容器尽可能通用（即只有一个Forward Container或者甚至可能只是一个简单的Container）在微粒中，不应该假设容器具有 .size() 和走两次（一次是为了计算大小，一次是为了得到结果集）是不可接受的。
我有一个解决方案，它比我想要的更复杂一些，并且依赖项更多，所以我希望在 3-5 行范围内。
问问题
375 次
1 回答
2
我假设“随机元素”是指均匀分布的元素。
由于您不知道序列的长度，并且您无法预先计算它，因此您必须逐步构建您的随机序列。所以让我们这样做，并希望我们使用的所有概率都很好地相加，所以我们最终得到了我们想要的结果。
我们将分两步进行。首先，决定绘制哪些序列号，然后如果需要，我们可以为它们选择随机顺序（从问题中不清楚）。我会称你的 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 大小排列。
免责声明：概率是个婊子，虽然这对我来说似乎是正确的，但我有可能错过了一些东西，最终结果不会均匀分布。其他人会很快告诉你。
于 2013-07-07T07:15:23.497 回答