如何生成列表的所有排列?例如:
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]
当前回答
如果用户希望在列表中保留所有排列,可以使用以下代码:
def get_permutations(nums, p_list=[], temp_items=[]):
if not nums:
return
elif len(nums) == 1:
new_items = temp_items+[nums[0]]
p_list.append(new_items)
return
else:
for i in range(len(nums)):
temp_nums = nums[:i]+nums[i+1:]
new_temp_items = temp_items + [nums[i]]
get_permutations(temp_nums, p_list, new_temp_items)
nums = [1,2,3]
p_list = []
get_permutations(nums, p_list)
其他回答
此解决方案实现了一个生成器,以避免在内存中保留所有排列:
def permutations (orig_list):
if not isinstance(orig_list, list):
orig_list = list(orig_list)
yield orig_list
if len(orig_list) == 1:
return
for n in sorted(orig_list):
new_list = orig_list[:]
pos = new_list.index(n)
del(new_list[pos])
new_list.insert(0, n)
for resto in permutations(new_list[1:]):
if new_list[:1] + resto <> orig_list:
yield new_list[:1] + resto
使用标准库中的itertools.permutations:
import itertools
list(itertools.permutations([1, 2, 3]))
从这里改编的是itertools.permutations如何实现的演示:
def permutations(elements):
if len(elements) <= 1:
yield elements
return
for perm in permutations(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
itertools.permutations文档中列出了两种替代方法
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
另一个基于itertools.product:
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
人们确实可以对每个排列的第一个元素进行迭代,正如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 2.6及以上版本:
import itertools
itertools.permutations([1, 2, 3])
这将作为生成器返回。使用列表(排列(xs))作为列表返回。
另一种解决方案:
def permutation(flag, k =1 ):
N = len(flag)
for i in xrange(0, N):
if flag[i] != 0:
continue
flag[i] = k
if k == N:
print flag
permutation(flag, k+1)
flag[i] = 0
permutation([0, 0, 0])