如何在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]
Eli Bendersk.. 436
从Python 2.6开始(如果您使用的是Python 3),您可以使用标准库工具:itertools.permutations.
import itertools list(itertools.permutations([1, 2, 3]))
如果您出于某种原因使用较旧的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)
bgbg,dbr:它使用了一个生成器,所以函数本身不会占用内存.它留给你如何使用all_perms返回的迭代器(假设你可以将每次迭代写入磁盘而不用担心内存).我知道这篇文章已经过时但是我正在写这篇文章是为了所有现在阅读它的人的利益.现在,最好的方法是使用许多人指出的itertools.permutations(). (54认同)
不只是*a*发电机.它使用嵌套的生成器,如果不清楚的话,每个生成器都会向调用堆栈中的前一个生成器生成.它使用O(n)内存,这很好. (17认同)
如果排列列表足够大,这个和其他递归解决方案可能会占用所有RAM (13认同)
它们还使用大型列表达到递归限制(并且死亡) (3认同)
Brian.. 330
在Python 2.6以后:
import itertools itertools.permutations([1,2,3])
(作为生成器返回.用于list(permutations(l))作为列表返回.)
从Python 2.6开始(如果您使用的是Python 3),您可以使用标准库工具:itertools.permutations.
import itertools list(itertools.permutations([1, 2, 3]))
如果您出于某种原因使用较旧的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')
#!/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]
当我交换列表的内容时,需要一个可变序列类型作为输入.例如perm(list("ball")),perm("ball")因为你不能改变字符串,所以不会工作.
这个Python实现的灵感来自Horowitz,Sahni和Rajasekeran的计算机算法一书中提出的算法.
此解决方案实现了一个生成器,以避免在内存中保留所有排列:
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
在我看来,一个非常明显的方式可能是:
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
在功能风格
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]
]
我使用了基于阶乘数系统的算法- 对于长度为n的列表,您可以按项目组合每个排列项目,从每个阶段的左侧项目中进行选择.第一项有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]]
这个方法是非递归的,但它在我的计算机上稍慢,xrange在n时引发错误!太大而无法转换为C长整数(对我来说n = 13).当我需要它时它已经足够了,但它不是一个很长的镜头的itertools.permutations.
人们确实可以迭代每个排列的第一个元素,如tzwenn的答案; 我更喜欢用这种方式编写这个解决方案:
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(elements) <= 1而不是0.它还具有更高的内存效率,因为它使用生成器函数(通过yield),就像Riccardo Reyes的解决方案一样.
请注意,此算法具有n factorial时间复杂度,其中n是输入列表的长度
在运行中打印结果:
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]
这是受使用列表理解的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
京公网安备 11010802040832号 | 京ICP备19059560号-6 