生成一组整数的不同大小的所有排列的算法？

Question

假设我有一个整数数组，例如 [3,4,2,7,8,5]

我如何从该数组生成不同大小的排列？

想获得所有可能的 2 对，或所有可能的 3 组？共 4 个？

我希望能够很快完成。

Answer 1

对于基于第一原理的语言不可知方法：枚举所有大小为 k 的子集（对于 k = 2, ..., n，其中 n 是数组的大小）。维基百科关于组合的文章在 enumeration. For each enumerated subset use the Johnson-Trotter algorithm 中有一节用于枚举它的排列。这种排列的总数很快就会变得非常大。例如，只有 10 个项目有 9,864,090

许多语言都有库支持。例如，它是 Python 中的一个简单的编程练习（使用它的 itertools 模块）。这是一个生成此类排列的生成器：

import itertools

def allPermutations(items):
    n = len(items)
    for k in range(2,n+1):
        for combo in itertools.combinations(items,k):
            for perm in itertools.permutations(combo):
                yield perm

例如，list(allPermutations([3,4,2,7,8,5])) 计算出从 [3,4,2,7,8,5] 中提取的所有 1950 个此类排列的列表。

Answer 2

您可以使用任何算法（如众所周知的 Narayana algorithm）生成大小为 N 的所有排列。

现在，如果在这个总排列序列中，您只考虑带有前缀的排列 (a₁, a₂, ... , a_k) 其中 a₁ < a₂ < ... < a_k，则所有这些排列的尾部将组成长度为N - k.

的所有可能排列的序列

这样，通过一次遍历所有长度 N 的排列，您可以生成长度 N 和更短的所有排列。

这是 C++ 实现的样子

#include <iostream>
#include <algorithm>
#include <iterator>

int main() 
{
  int a[] = { 2, 3, 4, 5, 7, 8 };

  do
  {
    for (auto ite = std::begin(a); ite != std::end(a); ++ite)
      if (std::is_sorted(std::begin(a), ite))
      {
        std::copy(ite, std::end(a), std::ostream_iterator<int>(std::cout));
        std::cout << std::endl;
      }

  } while (std::next_permutation(std::begin(a), std::end(a)));
}

（我冒昧地对您的输入集进行了预排序。）

以上显然不是最优的，因为在 for 循环中连续调用 std::is_sorted 将重复 re-scan/re-check 上一次迭代中已经检查过的内容。但同样，此实现仅用于说明目的。

现在的问题是您对这些排列的生成顺序是否满意。上述方法没有按长度分组。

或者，您可以遍历 all possible combinations，然后为每个组合生成所有可能的排列。

生成一组整数的不同大小的所有排列的算法？

Algorithm to generate all permutations of different sizes of a group of integers?

algorithm

permutation