algorithm - 寻找一种通用的、快速的、低内存的算法来输出数组的 N-out-of-M 组合而不重复

Question

我有一个球员阵列

$players = array('A','B','C','D','E','F');

我想获得所有可能的 3 方式完成。

1st 2nd 3rd
A   B   C
A   B   D
...
C   A   B
C   B   A
...
F   D   E
F   E   D

我有一些排列算法，但它必须是别的东西，因为排列中有 6 * 5 * 4 * 3 * 2 * 1 组合，这里只有 6 * 5 * 4

Answer 1

这是一些伪代码，可以打印 6 个组合中的 3 个而不重复：

for i = 1 to 6
  for j = 1 to 6
    if (j != i)
      for k = 1 to 6
        if (k != i && k != j)
          print(A[i], A[j], A[k])
        end if
      next k
    end if
  next j
next i

对于一般的 k-of-n 情况，请参阅：从 n 返回 k 个元素的所有组合的算法

Answer 2

给定您的排列算法，您可以分两步使用它来获得所需的排列。

首先，让我们考虑以下映射。给定输入为A1 A2 A3 A4 A5 ... An，一个值b1 b2 b3 b4 b5 ... bn表示如果为 1 则选择Ai，如果bi为 0 则不选择。

使用您的输入，例如：

0 0 1 1 0 1 -> C D F
0 1 0 0 1 1 -> B E F

现在您的算法可以如下所示：

• 取n元素的数量（在您的情况下为 6）和m您要选择的数量。

• 构造以下序列：

  0 0 0 ... 0 1 1 1 ... 1
  \____ ____/ \____ ____/
       V           V
     n - m         m
  

• 获取上述序列的所有排列，并为每个排列：

  • 查找m序列中标记的元素
  • m获取这些元素 的所有排列，并为每个排列：
    • 做你想做的！

Answer 3

您的问题是没有找到 6 个元素的所有排列。

您的问题是选择 3 个元素，然后检查其排列。

组合数 = C(6,3)*3！= 6！/3！= 6 * 5 * 4。

C(6,3) - 用于从 6 个元素中选择 3 个元素。（无论顺序如何）

3！- 用于订购 3 个选定的元素。

这是您应该获得的确切组合数量。（你也是）

但是，您可以使用排列算法来获取 6 个元素的所有排列。比，只需忽略最后 3 个元素，并从结果中删除重复项。

Answer 4

我可能是错的，但我认为你在这里有正确数量的可能排列。您在 6 名玩家数组中仅选择 3 名玩家。所以对于第一个玩家，你有 6 个可能性，对于第二个玩家，你有 5 个可能性，对于第三个玩家，你有 4 个可能性。

如果您决定最后有 4 个玩家而不是 3 个玩家，则可能的排列数量将是 6*5*4*3，依此类推。

我希望我的数学不会太老！