有效地从一组尺寸$ N $选择随机的大小为M $的子集

Question

这是我的问题的横向帖子 在 math.se 。

我有一个 $ n $ 项目，并希望随机选择 $ m $ 从它有效地设置（在时间复杂性方面）。此外，我希望以相等的概率选择所有可能的子集。显而易见的解决方案是从 $ 1 $ 到 $ n $ 并选择相应的元素，然后选择相应的元素然后重复 $ m $ 时间，而不是计算选择和已选择元素的事件。随着 $ m $ 方法 $ n $ ，因此，这变得越来越低。为 $ m> n / 2 $ 它会有意义，而是选择 $（nm）$ -set并返回其恭维。

对于 $ m $ 关闭 $ n / 2 $ ，我认为更好的解决方案将考虑每个 $ n $ 元素，并决定选择该元素或丢弃它，每次更新根据的挑选或丢弃的概率所选元素在之前丢弃的vs。具体地，算法将如下（Python）：

def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

. 但是，我担心这可能不会导致以相等概率选择的每个子集。

我有两个问题。首先，该算法是否选择了具有相同概率的子集（如果是，我想证明它确实，如果不是我也喜欢它没有的证据。其次，更广泛地我想知道这个问题存在的解决方案是什么。显然，如果 $ m << n $ 那么第一个方法比第二个方法更好，在某些时候第二种方法（如果它实际上工作）更好第一的。此外，完全不同的方法可能是最佳的。

Answer 1

元素 $ 1 $ 所属的概率属于一个随机 $ m $ -subset的< SPAN Class=“Math-Container”> $ N $ -Element Set是 $ M / N $ 。因此，您应该在子集中包含 $ 1 $ 概率 $ m / n $ 。

如果将 $ 1 $ 放入子集中，则留下选择 $（m-1）$ -subset的 $（n-1）$ -element集合。

如果您没有将 $ 1 $ 放入子集中，那么您将留下选择 $ m $ < / span> -subset的 $（n-1）$ -Element集合。

这意味着您必须略微更新您的算法，替换 $ m $ 使用 $ m-| l | $ 。

生成的算法有点类似于水库采样。

具有一些相似之处的第三种方法是生成 $ 1，\ ldots，n $ 的随机排列，并选择第一个 $ M $ 条目。

所有这些方法的缺点是它们在时间中运行 $ \ theta（n）$ ，而for $ m \ ll \ sqrt {n} $ ，您的第一个算法在（预期）时间 $ \ tilde \ theta（m）$ 。

我们可以在 $ \ theta（n）$ 运行时间上提高。我们将生成一个随机排序 $ m $ -subset给定 $ m $ indices $ i_1，\ ldots，i_m $ ，其中 $ i_j \ in \ {1，\ ldots，n-（j-1）\} $ < / span>。 $ j $ '子集中的th元素将是 $ i_j $ <跨越类=“math-container”> $ \ {1，\ ldots，n \} $ 尚未选择的号码。

为了完成算法的描述，我们需要解决以下问题：给定 $ s \ subseteq \ {1，\ ldots，n \} $ $ i $ ，找到 $ i $ $ \ overline {s} $ 。我们可以假设 $ s $ 存储在一个结构（如自平衡二叉树）中，这可以有效地回答以下类型的查询：给定<跨度类=“math-container”> $ x $ ， $ s $ 中的多少元素小于 $ x $ 。然后，我们可以找到 $ i $ $ \ overline {s} $ 使用二进制文件搜索。

总的来说，该算法在 $ \ tilde \ theta（m）$ 中运行 $ m $ < / span>，其中tilde隐藏了 $ n $ 中的对数的因子。 （当<跨越类=“math-container”> $ m \ ll \ sqrt {n} $ 时，我们可以使用您的第一个方法，从而摆脱此依赖性 $ n $ 。）