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

Question

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

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

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

我希望能够很快完成。

Answer 1

对于基于第一原理的语言不可知方法:枚举所有大小为 k 的子集(对于 k = 2, ..., n，其中 n 是数组的大小)。维基百科关于组合的文章有一节关于他们的 enumeration .对于每个枚举子集，使用 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 中提取的所有 1950 个此类排列的列表,2,7,8,5]。