如何在Python中生成一个列表的所有排列
如何在Python中生成一个列表的所有排列，与列表中元素的types无关？
例如：
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] 编辑：Eliben指出类似于我的解决scheme，虽然更简单，所以我select它作为接受的答案，虽然Python 2.6 +具有itertools模块中的内置解决scheme：
import itertools itertools.permutations([1, 2, 3])
从Python 2.6开始 （如果您使用的是Python 3），您可以使用标准库工具： itertools.permutations 。
如果您使用较旧的Python（<2.6）出于某种原因，或者只是想知道它是如何工作的，可以参考http://code.activestate.com/recipes/252178/ ：
def all_perms(elements): if len(elements) <=1: yield elements else: for perm in all_perms(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, nr, -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)
而在Python 2.6之后：
import itertools itertools.permutations([1,2,3])
（作为生成器返回，使用list(permutations(l))作为列表返回。）
以下代码仅适用于Python 2.6及更高版本
首先，导入itertools ：
import itertools
排列（顺序重要）：
print list(itertools.permutations([1,2,3,4], 2)) [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
组合（顺序无关紧要）：
print list(itertools.combinations('123', 2)) [('1', '2'), ('1', '3'), ('2', '3')]
笛卡儿积（有几个迭代）：
print list(itertools.product([1,2,3], [4,5,6])) [(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]
笛卡儿积（有一个迭代本身）：
print list(itertools.product([1,2], repeat=3)) [(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
def permutations(head, tail=''): if len(head) == 0: print tail else: for i in range(len(head)): permutations(head[0:i] + head[i+1:], tail+head[i])
称为：
permutations('abc')
这个解决scheme实现了一个生成器，以避免保持所有的内存排列：
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
#!/usr/bin/env python def perm(a,k=0): if(k==len(a)): print a else: for i in xrange(k,len(a)): a[k],a[i] = a[i],a[k] perm(a, k+1) a[k],a[i] = a[i],a[k] perm([1,2,3])
输出：
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]
当我交换列表的内容时，需要一个可变的序列types作为input。 例如， perm(list("ball"))将起作用，而perm("ball")不会因为你不能改变一个string。
这个Python的实现受Horowitz，Sahni和Rajasekeran在“ 计算机algorithm ”一书中介绍的algorithm的启发 。
以下代码是给定列表的就地排列，作为生成器实现。 由于它仅返回对列表的引用，所以不应该在生成器之外修改列表。 该解决scheme是非recursion的，所以使用低内存。 也可以在input列表中使用多个元素的副本。
def permute_in_place(a): a.sort() yield list(a) if len(a) <= 1: return first = 0 last = len(a) while 1: i = last - 1 while 1: i = i - 1 if a[i] < a[i+1]: j = last - 1 while not (a[i] < a[j]): j = j - 1 a[i], a[j] = a[j], a[i] # swap the values r = a[i+1:last] r.reverse() a[i+1:last] = r yield list(a) break if i == first: a.reverse() return if __name__ == '__main__': for n in range(5): for a in permute_in_place(range(1, n+1)): print a print for a in permute_in_place([0, 0, 1, 1, 1]): print a print
在我看来，一个很明显的方法可能也是：
def permutList(l): if not l: return [[]] res = [] for e in l: temp = l[:] temp.remove(e) res.extend([[e] + r for r in permutList(temp)]) return res
在function风格
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]]
list2Perm = [1, 2.0, 'three'] listPerm = [[a, b, c] for a in list2Perm for b in list2Perm for c in list2Perm if ( a != b and b != c and a != c ) ] print listPerm
输出：
[ [1, 2.0, 'three'], [1, 'three', 2.0], [2.0, 1, 'three'], [2.0, 'three', 1], ['three', 1, 2.0], ['three', 2.0, 1] ]
请注意，此algorithm具有n factorial时间复杂度，其中n是input列表的长度
在运行中打印结果：
global result result = [] def permutation(li): if li == [] or li == None: return if len(li) == 1: result.append(li[0]) print result result.pop() return for i in range(0,len(li)): result.append(li[i]) permutation(li[:i] + li[i+1:]) result.pop()
例：
permutation([1,2,3])
输出：
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
我使用了一个基于阶乘数字系统的algorithm – 对于长度为n的列表，可以逐项组合每个置换，从每个阶段剩下的项目中进行select。 第一个项目有n个选项，第二个项目有n-1个选项，最后一个选项只有一个选项，因此可以使用阶乘数系统中的数字的数字作为索引。 这样数字0到n！-1对应于字典顺序中的所有可能的排列。
from math import factorial def permutations(l): permutations=[] length=len(l) for x in xrange(factorial(length)): available=list(l) newPermutation=[] for radix in xrange(length, 0, -1): placeValue=factorial(radix-1) index=x/placeValue newPermutation.append(available.pop(index)) x-=index*placeValue permutations.append(newPermutation) return permutations permutations(range(3))
输出：
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
这种方法是非recursion的，但是在我的电脑上稍微慢一点，而且nrange时会引发一个错误！ 太大而无法转换为C长整型（对我而言，n = 13）。 当我需要的时候已经足够了，但是没有一个迭代的itertools.permutations。
人们确实可以迭代每个排列的第一个元素，就像tzwenn的答案一样; 我更喜欢这样写这个解决scheme：
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
这个解决scheme快了大约30％，显然感谢len(elements) <= 1而不是0的recursion。 它也是更高的内存效率，因为它使用了一个生成器函数（ yield ），就像在Riccardo Reyes的解决scheme中一样。
对于性能，一个由Knuth启发的解决scheme（p22）：
from numpy import empty, uint8 from math import factorial def perms(n): f = 1 p = empty((2*n-1, factorial(n)), uint8) for i in range(n): p[i, :f] = i p[i+1:2*i+1, :f] = p[:i, :f] # constitution de blocs for j in range(i): p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f] # copie de blocs f = f*(i+1) return p[:n, :]
复制大块内存可节省时间 – 比list(itertools.permutations(range(n))快20倍list(itertools.permutations(range(n)) ：
In [1]: %timeit -n10 list(permutations(range(10))) 10 loops, best of 3: 815 ms per loop In [2]: %timeit -n100 perms(10) 100 loops, best of 3: 40 ms per loop
原谅我的python文盲，因为我不会提供python的解决scheme。 由于我不知道python 2.6用来生成排列的方法，eliben看起来像Johnson-Trotter排列生成，所以您可以在Wikipedia上查找关于Permutations和他们这一代的文章 ，看起来很像Myrvold和Ruskey在论文中的非排他性函数。
在我看来，这可以用在发生器中，就像在其他答复一样，以大大减less内存要求。 请记住，排列不会按字典顺序排列。
这是一个在列表上工作的algorithm，无需创build类似于Ber的解决scheme的新的中间列表（ 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
from __future__ import print_function def perm(n): p = [] for i in range(0,n+1): p.append(i) while True: for i in range(1,n+1): print(p[i], end=' ') print("") i = n - 1 found = 0 while (not found and i>0): if p[i]<p[i+1]: found = 1 else: i = i - 1 k = n while p[i]>p[k]: k = k - 1 aux = p[i] p[i] = p[k] p[k] = aux for j in range(1,(ni)/2+1): aux = p[i+j] p[i+j] = p[n-j+1] p[n-j+1] = aux if not found: break perm(5)
这受到了Haskell实现使用列表理解的启发：
def permutation(list): if len(list) == 0: return [[]] else: return [[x] + ys for x in list for ys in permutation(delete(list, x))] def delete(list, item): lc = list[:] lc.remove(item) return lc
recursion之美：
>>> import copy >>> def perm(prefix,rest): ... for e in rest: ... new_rest=copy.copy(rest) ... new_prefix=copy.copy(prefix) ... new_prefix.append(e) ... new_rest.remove(e) ... if len(new_rest) == 0: ... print new_prefix + new_rest ... continue ... perm(new_prefix,new_rest) ... >>> perm([],['a','b','c','d']) ['a', 'b', 'c', 'd'] ['a', 'b', 'd', 'c'] ['a', 'c', 'b', 'd'] ['a', 'c', 'd', 'b'] ['a', 'd', 'b', 'c'] ['a', 'd', 'c', 'b'] ['b', 'a', 'c', 'd'] ['b', 'a', 'd', 'c'] ['b', 'c', 'a', 'd'] ['b', 'c', 'd', 'a'] ['b', 'd', 'a', 'c'] ['b', 'd', 'c', 'a'] ['c', 'a', 'b', 'd'] ['c', 'a', 'd', 'b'] ['c', 'b', 'a', 'd'] ['c', 'b', 'd', 'a'] ['c', 'd', 'a', 'b'] ['c', 'd', 'b', 'a'] ['d', 'a', 'b', 'c'] ['d', 'a', 'c', 'b'] ['d', 'b', 'a', 'c'] ['d', 'b', 'c', 'a'] ['d', 'c', 'a', 'b'] ['d', 'c', 'b', 'a']
这个algorithm是最有效的，它避免了recursion调用中的数组传递和操作，在Python 2，3中工作：
def permute(items): length = len(items) def inner(ix=[]): do_yield = len(ix) == length - 1 for i in range(0, length): if i in ix: #avoid duplicates continue if do_yield: yield tuple([items[y] for y in ix + [i]]) else: for p in inner(ix + [i]): yield p return inner()
用法：
for p in permute((1,2,3)): print(p) (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
def pzip(c, seq): result = [] for item in seq: for i in range(len(item)+1): result.append(item[i:]+c+item[:i]) return result def perm(line): seq = [c for c in line] if len(seq) <=1 : return seq else: return pzip(seq[0], perm(seq[1:]))
我看到这些recursion函数内部进行了很多迭代，而不是纯粹的recursion…
所以对于那些不能遵守单一循环的人来说，这是一个完全不必要的完全recursion解决scheme
def all_insert(x, e, i=0): return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else [] def for_each(X, e): return all_insert(X[0], e) + for_each(X[1:],e) if X else [] def permute(x): return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0]) perms = permute([1,2,3])
生成所有可能的排列
我正在使用python3.4：
def calcperm(arr, size): result = set([()]) for dummy_idx in range(size): temp = set() for dummy_lst in result: for dummy_outcome in arr: if dummy_outcome not in dummy_lst: new_seq = list(dummy_lst) new_seq.append(dummy_outcome) temp.add(tuple(new_seq)) result = temp return result
testing案例：
lst = [1, 2, 3, 4] #lst = ["yellow", "magenta", "white", "blue"] seq = 2 final = calcperm(lst, seq) print(len(final)) print(final)
另一个scheme
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])
这种方式比我看到的替代scheme更好，请查看。
def permutations(arr): if not arr: return print arr for idx, val in enumerate(arr): permutations(arr[:idx]+arr[idx+1:])
对于Python，我们可以使用itertools并导入排列和组合来解决您的问题
from itertools import product, permutations A = ([1,2,3]) print (list(permutations(sorted(A),2)))
