algorithm - 在Python,如何生成所有排列所有的列表

如何在python中生成列表的所有排列?

例如:


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]


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

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

 

此解决方案实现生成器,以避免保留内存中的所有排列:


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

下面的代码是一个给定列表的位置排列,作为生成器实现,解决方案是非递归的,因此内存占用少。在输入列表中同时使用多个元素的副本。


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


#!/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]


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


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

函数风格




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


...