从大小为N的数组生成一组M个元素

Question

我正在尝试了解以下任务的解决方案：从大小为N的数组中随机生成一组M个元素。每个元素的选择概率必须相同。

我找到了以下解决方案（我已经读过这个问题，但是它不能回答我的问题）：

int rand(Random random, int min, int max) {

  return random.nextInt(1 + max - min) + min;

}

char[] generateArray(char[] original, int subsetSize) {

  char[] subset = new char[subsetSize];

  Random random = new Random();

  for (int i = 0; i < subsetSize; i++) {

    subset[i] = original[i];

  }

  for (int i = subsetSize; i < original.length; i++) {

    int r = rand(random,0, i);

    boolean takeIthElement = r < subsetSize;

    if (takeIthElement) {

      subset[r] = original[i];

    }

  }

  return subset;

}

// rand() function returns inclusive value 

// i.e. rand(0, 5) will return from 0 to 5

可以在“破解编码访谈”一书中找到此代码（Section Hard，任务3）。作者解释如下：

假设我们有一种算法可以m从size数组中提取随机元素集n - 1。我们如何使用该算法m从大小数组中提取随机元素集n？我们首先可以从前几个n - 1元素中随机抽取大小为m的集合。然后，我们只需要确定是否array[n]应将其插入子集即可（这将需要从子集中抽出一个随机元素）。一种简单的方法是从0到n中选择一个随机数k。如果k < m，然后插入array[n]到subset[k]。这都将“公平地”（即具有成比例的概率）插入array[n]进入子集并“公平地”从子集中删除随机元素。迭代编写甚至更干净。在这种方法中，我们将数组子集初始化为m原始数组中的第一个元素。然后，我们遍历数组，从element开始，每当m插入array[i]到（随机）位置的子集中。kk < m

我想作者想说我们需要生成的不是set，而是数组。所以，我认为正确的任务描述应该是：随机产生一个阵列M个元素的大小从N的一个阵列的每个元素必须具有被选择的同等概率。

如果为true，则上述代码将无法正常工作。原因：

例如，我们有一个数组{'1', '2', 'a', 'b'}和m = 2

因此，我们应该具有生成以下几组的资格概率：

{1, 2}; {2, 1}; {1, a}; {a, 1}; {1, b}; {b, 1}; {a, 2}; {2, a}; {b, 2}; {2, b}; {a, b}; {b, a}

我在这里担心的是，该函数将永远不会生成以下集合： {2, 1}; {2, a}; {2, b}

因此，这意味着它是不正确的。

Answer 1

首先，从解释和代码中可以很清楚地看出作者所设定的含义，就像他们写的一样。在实际的实现中，可以将集合建模为数组，这并不意味着任何事情。在编程方面的挑战中，人们通常使用相当简单的结构-如数组代替java.util.Set。因此，任务基本上是：M从size数组中随机选择一组元素N。假设N >= M。现在最困难的部分：为什么该算法会产生正确的结果？仅看算法，很难理解它是如何工作的以及为什么。我认为这是因为算法实际上是递归构造的，而递归finall在迭代中没有展开。让我们从递归开始。假设我们能够M从size数组中随机选择元素N - 1。我们如何M从大小数组中选择元素N？由于数组中有一个“新”元素，因此我们可以用其中的一个替换选定的元素-或保留原样。但是我们必须保留随机属性。可以从中选择一组M元素。可以从中选择 一组元素。N-1(N-1)! / M!*(N-1 - M)!MNN! / M!*(N - M)!这意味着我们应该保留(N-M)/N概率集，并用概率替换元素之一M/N。我们还必须选择要用1/M概率替换的元素。让我们看看它在代码中的外观。假设subset是我们从中随机选择的一组M元素N-1。首先，我们应该决定是否替换其中一个元素。我们需要一个(N-M)/N概率。为此，我们可以在0和之间生成一个随机数N。如果该数字小于M，我们将替换。boolean replace = rand(random, 0, N) < M;if (replace) {&nbsp; &nbsp;// then replace}现在我们必须选择要替换的元素之一。由于我们将数组建模为一个集合，因此我们可以简单地在0和之间M - 1（包括两者之间）随机选择一个索引。这样我们得到：boolean replace = rand(random, 0, N) < M;if (replace) {&nbsp; &nbsp;subset[rand(random, 0, M - 1)] = original[N];}在这里我们可以注意到，如果我们的第一个随机值（rand(random, 0, N)）小于M，则它是0和之间的一个随机值M-1。因此，我们不需要第二个rand：int r = rand(random, 0, N);boolean replace = r < M;if (replace) {&nbsp; &nbsp;subset[r] = original[N];}其余的应该是微不足道的。递归的基本情况是M == N。在这种情况下，我们什么都不会替换，因此所选元素的集合就是原始数组的简单形式。之后，可以将递归简单地编码为一个循环。i代表N每个步骤-这为您提供了自己的代码。

Answer 2

我认为作者想说我们需要生成的不是set而是array。不，作者真正的意思是集合，但碰巧将结果集合存储在数组中。通过说结果是一个集合，就意味着值的顺序无关紧要，这意味着{1, 2}和{2, 1}是相同的集合。鉴于此，它是确定这一结果永远不会{2, 1}，只要结果与值的概率1和2为1/6，即无序台（套）的概率。如果您想要一个有序的结果，即列出它们时有12个不同的结果，那么最简单的解决方案是改组原始数组并采用第一个M值。这样可以保证所有结果的概率均等，并且不会重复。通常使用Fisher-Yates shuffle来进行数组改组，这是对数组进行迭代并将该元素与先前的元素随机交换。问题中的算法是该算法的一种变体。如果跳过前M个值的随机改组，则顺序无关紧要。然后，它会随机地将后续元素与随机元素交换，但是如果随机位置> M不会发生交换，并且交换掉的值将被简单丢弃，因为它最终会出现在结果集之外。因此，这是经过修改的Fisher-Yates随机播放，可以在原始数组的副本中生成随机子集，但是经过优化，可以跳过不必要的随机播放，因为我们需要一个集合，而不是有序列表/数组，而我们只想要一个子集，而不是所有值。

Answer 3

如何用数学证明呢？您的第二个for循环运行两次，首先i等于2，然后i等于3。当i为2时，r变为0、1或2，每个概率为1/3。因此，chara将以索引0或1或根本不索引的形式移到您的结果中，每个概率为1/3。现在它是[a，2]，[1，a]或[1，2]。当i为3时，r为0、1、2或3。b以1/4的概率移至索引0，以1/4的概率移至索引1，并且没有以1/2的概率移至任何位置。在下表中，我给出了所有可能情况下的结果。值下r，0，1和2，是在第一次迭代（可能的值i= 2）。右边的或是r第二次迭代中的可能值。r&nbsp; &nbsp; 0&nbsp; &nbsp; &nbsp; &nbsp;1&nbsp; &nbsp; &nbsp; &nbsp;2&nbsp; &nbsp; &nbsp; &nbsp;30&nbsp; [b, 2]&nbsp; [a, b]&nbsp; [a, 2]&nbsp; [a, 2]1&nbsp; [b, a]&nbsp; [1, b]&nbsp; [1, a]&nbsp; [1, a]2&nbsp; [b, 2]&nbsp; [1, b]&nbsp; [1, 2]&nbsp; [1, 2]因此，在表中您可以读取到，如果r两次都为0，则您的方法将返回[b, 2]，等等。表中的12个单元格中的每个单元具有相等的概率，即1/12。让我们检查一下：[1，2]，[1，a]，[1，b]，[a，2]和[b，2]分别存在两次。[a，b]和[b，a]各自出现一次，但是它们是同一集合，因此该集合也出现两次。这涵盖了所有可能的子集，因此它们的可能性也相同。