如何生成列表的所有排列?例如:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
如何生成列表的所有排列?例如:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
当前回答
人们确实可以对每个排列的第一个元素进行迭代,正如tzwen的答案。然而,这样编写此解决方案更有效:
def all_perms(elements):
if len(elements) <= 1:
yield elements # Only permutation possible = no permutation
else:
# Iteration over the first element in the result permutation:
for (index, first_elmt) in enumerate(elements):
other_elmts = elements[:index]+elements[index+1:]
for permutation in all_perms(other_elmts):
yield [first_elmt] + permutation
这个解决方案大约快了30%,显然是因为递归以len(元素)<=1而不是0结尾。它的内存效率也高得多,因为它使用了一个生成器函数(通过yield),就像Riccardo Reyes的解决方案一样。
其他回答
我的Python解决方案:
def permutes(input,offset):
if( len(input) == offset ):
return [''.join(input)]
result=[]
for i in range( offset, len(input) ):
input[offset], input[i] = input[i], input[offset]
result = result + permutes(input,offset+1)
input[offset], input[i] = input[i], input[offset]
return result
# input is a "string"
# return value is a list of strings
def permutations(input):
return permutes( list(input), 0 )
# Main Program
print( permutations("wxyz") )
def permutations(head, tail=''):
if len(head) == 0:
print(tail)
else:
for i in range(len(head)):
permutations(head[:i] + head[i+1:], tail + head[i])
称为:
permutations('abc')
如果不想使用内置方法,例如:
import itertools
list(itertools.permutations([1, 2, 3]))
你可以自己实现permute函数
from collections.abc import Iterable
def permute(iterable: Iterable[str]) -> set[str]:
perms = set()
if len(iterable) == 1:
return {*iterable}
for index, char in enumerate(iterable):
perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])
return perms
if __name__ == '__main__':
print(permute('abc'))
# {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
print(permute(['1', '2', '3']))
# {'123', '312', '132', '321', '213', '231'}
这里有一个算法,它在不创建新的中间列表的情况下处理列表,类似于Ber在https://stackoverflow.com/a/108651/184528.
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
print p
您可以在这里亲自尝试代码:http://repl.it/J9v
功能性风格
def addperm(x,l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
print perm([ i for i in range(3)])
结果:
[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]