从大小为N的数组生成一组M个元素的概率[重复]

我试图了解以下任务的解决方案: 从一个大小为N的数组中随机生成一组M个元素。每个元素被选中的概率必须相等。

this question ,和 this one ,但我还有一些问题太长,无法发表评论):

int rand(int min, int max) { 
  return min + (int)(Math.random() * (max - min + 1));
}

int[] generateSet(int[] arr, int m, int n) {
    if (n + 1 == m) { //base case
        int[] set = new int[m];
        for (int k = 0; k < m; k++) {
            set[k] = arr[k];
        }
        return set;
    }

    int[] set = generateSet(arr, m, n - 1);
    int r = rand(0, n);
    if (r < m) set[r] = arr[n];
    return set;
}
// rand() function returns inclusive value 
// i.e. rand(0, 5) will return from 0 to 5

这段代码可以在“破解编码面试”一书中找到(第三部分,任务3)。

假设我们有一个算法,可以从 m n - 1 . 我们如何使用这个算法来抽取 米 大小数组中的元素 n n-1个 元素。那么,我们只需要决定 array[n] 应该插入到我们的子集中(这需要从中取出一个随机元素)。一个简单的方法是从0到n中选择一个随机数k k < m ,然后插入 数组[n] subset[k] . 这将“公平”(即,按比例概率)插入 数组[n] 然后“公平地”从子集中移除一个随机元素。 这甚至可以更简洁地进行迭代编写。在这种方法中,我们将数组子集初始化为第一个 ,插入 array[i] 进入(随机)位置的子集 k 无论何时 k<m

我完全理解这个基地案例。它如果我们有一个大小数组 N 和 M == N 因此,我们应该先回来 M

更难的是(递归的情况),我根本不懂。

1. 从大小数组 N - 1
2. 现在代码应该决定是否添加“new”元素 arr[N] 到片场去

3. 有可能吗 M / N 代码决定是否添加“新”元素。随机工作如下:

   1. 生成随机数 r 0 和 N
   2. (r < m) 意思是 r 生成时使用 可能性
   3. 如果 (米) 1 / M

我不明白以下几点: 假设我们有一个包含N-1个元素的盒子。我们从中提取M元素。因此,获得一组元素的概率为:

Pa(get any set with M elements using N-1 elements) = 1 / ((N-1)! / M!(N-1-M)!) = M!(N-1-M)!) / (N-1)!

很明显,如果我们把所有的元素放回盒子里,再把M元素放回盒子里,我们就会创建一个概率相等的集合。

好吧,让我们假设我们取M元素。因此,盒子现在包含 N-1-M 元素。

这就是递归案例的开始: 现在我们从口袋里拿一个作为新元素。现在我们应该决定是否修改集合。

从这一点开始,我完全不知道下一步该怎么办。我的猜测是:

当我们有N-1个元素时,用M个元素生成任何集合的概率是:

Pa(get any set with M elements using N-1 elements) = M!(N-1-M)!) / (N-1)!

但我们又增加了一个新元素。现在我们应该生成概率必须等于 Pa 但现在新的可能性是:

Pb = 1 / (N! / !M(N-M)!) = M!(N-M)!) / N!

所以我们要想办法 转换 以某种方式 Pb 到 即

!M(N-M)!) / N! 到 !M(N-1-M)!) / (N-1)!

再加上一些魔力(我仍然不明白它是如何工作的)递归case可以做到:

2. 如果R等于Y,则调用rand(0,M)生成索引,该索引将用新元素更新