假设我有一个整数数组,例如[3,4,2,7,8,5]
如何从该数组生成不同大小的排列?
比如得到所有可能的2对,或者所有可能的3对共4个?
我希望能很快做到。

最佳答案

对于与语言无关的方法,从第一个原则出发:枚举大小为k的所有子集(对于k=2,…,n,其中n是数组的大小)维基百科关于组合的文章有一个关于它们的enumeration的部分。对于每个枚举子集,使用Johnson-Trotter algorithm枚举其置换这样的排列的总数变得非常大,非常快例如,只有10个项目就有9864090个
许多语言都有库支持例如,它是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个这样的置换的列表。

09-10 03:01
查看更多