如何在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]
标准库中有一个用于此的功能:itertools.permutations
。
import itertools
list(itertools.permutations([1, 2, 3]))
如果出于某种原因你想自己实现它或者只是好奇地知道它是如何工作的,那么这是一种不错的方法,取自 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)
如果排列的列表足够大,则此递归解决方案和其他递归解决方案都可能会耗尽所有RAM。
它们还可以通过较大的列表达到递归限制(并消亡)
bgbg,dbr:使用生成器,因此该函数本身不会占用内存。它由您决定如何使用all_perms返回的迭代器(例如,您可以将每个迭代写入磁盘,而不必担心内存)。我知道这篇文章已经过时了,但是我写这篇文章是为了让现在阅读它的每个人都受益。同样现在,最好的方法是使用许多人指出的itertools.permutations()。
不只是一个发电机。它使用嵌套的生成器,如果不清楚,每个生成器将在调用堆栈中生成上一个生成器。它使用O(n)内存,这很好。
PS:我用
for i in range(len(elements))
代替修复了它for i in range(len(elements)+1)
。实际上,单选元素elements[0:1]
可以位于len(elements)
不同的位置,结果不是len(elements)+1
。