假设我有一个整数数组,例如[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个这样的置换的列表。