从大小为N的数组生成一组M个元素的概率[重复]-Java 学习之路

这个问题与以下内容完全相同：

Generate a set of M elements from an array of size N 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

这段代码可以在“Cracking the coding interview”（Section Hard，Task 3）一书中找到 . 作者解释如下：

假设我们有一个算法可以从大小为n的数组中拉出一组随机的m个元素 . 我们如何使用这个算法从大小为n的数组中提取一组随机的m个元素？我们可以先从第一个n - 1个元素中拉出一个随机的大小为m的集合 . 然后，我们只需要决定是否应该将array [n]插入到我们的子集中（这需要从中拉出一个随机元素） . 一个简单的方法是从0到n中选择一个随机数k . 如果k <m，则将array [n]插入子集[k] . 这将“公平地”（即，具有比例概率）插入阵列[n]到子集中并且“公平地”从子集中移除随机元素 . 迭代编写更加清晰 . 在这种方法中，我们将数组子集初始化为原始的前m个元素 . 然后，我们遍历数组，从元素m开始，每当k <m时将array [i]插入到（随机）位置k的子集中 .

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

然而，我完全不理解的是困难部分（递归案例） .

代码从大小为 N - 1 的数组生成大小 M 的集合
现在代码应该决定是否添加"new" element arr[N] 到集合中
使用概率 M / N 代码决定是否添加"new"元素 . 随机工作如下：
在 0 和 N 之间生成随机数 r
如果 (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!

所以我们需要找到一种方法 convert 某种方式 Pb 到 Pa 即

!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值？

1 回答

1
有 choose(n, m) = n! / (m! (n-m)!) 种方法可以从包含 n 元素的集合中选择 m 元素 . 您希望以相同的概率选择这些安排中的任何一个 .

关于是否采用给定元素，您有两种选择：
- 选择"this"元素，并从 n-1 元素中选择 m-1 元素;
- 或不选择"this"元素，并从 n-1 元素中选择 m 元素 .
你必须以一种能产生相同频率的任何安排的方式做出选择
```
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
```
按要求 .
回复于 2024-04-26T11:33:21+08:00

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

更新：

1 回答

相关问题