java - 从大小为 N 的数组生成一组 M 个元素的概率

Question

这个问题在这里已经有了答案:





Generate a set of M elements from an array of size N

(3 个回答)


3年前关闭。




我正在尝试了解以下任务的解决方案:
从大小为 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)。
作者解释如下:

Suppose we have an algorithm that can pull a random set of m elements from an array of size n - 1. How can we use this algorithm to pull a random set of m elements from an array of size n? We can first pull a random set of size m from the first n - 1 elements. Then, we just need to decide if array[n] should be inserted into our subset (which would require pulling out a random element from it). An easy way to do this is to pick a random number k from 0 through n. If k < m, then insert array[n] into subset[k]. This will both "fairly" (i.e., with proportional probability) insert array[n] into the subset and "fairly" remove a random element from the subset. This is even cleaner to write iteratively. In this approach, we initialize an array subset to be the first m elements in original. Then, we iterate through the array, starting at element m, inserting array[i] into the subset at (random) position k whenever k < m.

我完全理解基本情况。它说:如果我们有一个大小为 N 的数组和 M == N ，因此，我们应该首先返回 M数组中的元素，因为它们中的每一个都将以相等的概率被选择。

然后是我根本不理解的困难部分(递归案例)。

代码生成一组大小 M来自大小为 N - 1 的数组

现在代码应该决定是否添加"new"元素arr[N]到集合

概率为 M / N代码决定添加或不添加"new"元素。随机作品如下:

生成随机数r 0之间和 N

如果 (r < m)这意味着 r使用 M / N 生成概率

如果 (r < m)这意味着有概率 1 / M我们将更改集合中的 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)!
但是我们又添加了一个新元素。现在我们应该生成任意 M 个元素的集合，其概率必须等于 Pa。 .
但现在新的概率是:
Pb = 1 / (N! / !M(N-M)!) = M!(N-M)!) / N!
所以我们需要想办法 转换 不知何故 Pb至 Pa IE。
!M(N-M)!) / N!至 !M(N-1-M)!) / (N-1)!
并通过一些魔术(我仍然不明白它是如何工作的)递归案例来做到这一点:

调用 R = rand(0, X) (我不知道 X 是什么)。如果 R 等于某个 Y(我不知道 Y 值是多少)，这意味着我们应该使用我们的新元素。

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

进行更新

题:
1. 如何计算 X 和 Y 值？

Answer 1

有choose(n, m) = n! / (m! (n-m)!)选择方式m包含 n 的集合中的元素元素。您想以相同的概率选择这些安排中的任何一种。

对于是否采用给定元素，您有两种选择:

选择“this”元素，然后选择 m-1来自 n-1 的元素元素；

或不选择“this”元素，而是选择 m来自 n-1 的元素元素。

您必须以一种能够产生任何频率相同的安排的方式做出选择

P(pick) = (# arrangements which pick "this" element) / (# arrangements)
        = (# arrangements which pick "this" element) / (# arrangements which pick "this" element + # arrangements which do not pick "this" element)
        = A / (A + B)

介绍 A和 B为了符号方便。

A = choose(n-1, m-1) 
  = (n-1)! / (m-1)!(n-m)!

B = choose(n-1, m) 
  = (n-1)! / m!(n-m-1)!

A 的分子和分母相乘和 B使它们的公因数为 (n-1)! / m!(n-m)! :

A = m     * (n-1)! / m!(n-m)!
B = (n-m) * (n-1)! / m!(n-m)!

然后:

P = m / (m + n - m)
  = m / n

按要求。