# algorithm - 在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])

``````

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

``````

``````
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))`作为列表返回)

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

``````

``````
if len(head) == 0: print tail
else:

``````

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

``````

``````

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

``````