如何在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&#xFF09; 。

 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)))