如何生成列表的所有排列?例如:
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]
如何生成列表的所有排列?例如:
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]
当前回答
我使用了一种基于阶乘数系统的算法——对于长度为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。
其他回答
人们确实可以对每个排列的第一个元素进行迭代,正如tzwen的答案。然而,这样编写此解决方案更有效:
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(元素)<=1而不是0结尾。它的内存效率也高得多,因为它使用了一个生成器函数(通过yield),就像Riccardo Reyes的解决方案一样。
功能性风格
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]]
对于性能,一个由Knuth启发的numpy解决方案(第22页):
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, :]
复制大量内存可节省时间-它比列表(itertools.permutations(range(n))快20倍:
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
如果有人喜欢这个丑陋的单行线(虽然只适用于字符串):
def p(a):
return a if len(a) == 1 else [[a[i], *j] for i in range(len(a)) for j in p(a[:i] + a[i + 1:])]
from typing import List
import time, random
def measure_time(func):
def wrapper_time(*args, **kwargs):
start_time = time.perf_counter()
res = func(*args, **kwargs)
end_time = time.perf_counter()
return res, end_time - start_time
return wrapper_time
class Solution:
def permute(self, nums: List[int], method: int = 1) -> List[List[int]]:
perms = []
perm = []
if method == 1:
_, time_perm = self._permute_recur(nums, 0, len(nums) - 1, perms)
elif method == 2:
_, time_perm = self._permute_recur_agian(nums, perm, perms)
print(perm)
return perms, time_perm
@measure_time
def _permute_recur(self, nums: List[int], l: int, r: int, perms: List[List[int]]):
# base case
if l == r:
perms.append(nums.copy())
for i in range(l, r + 1):
nums[l], nums[i] = nums[i], nums[l]
self._permute_recur(nums, l + 1, r , perms)
nums[l], nums[i] = nums[i], nums[l]
@measure_time
def _permute_recur_agian(self, nums: List[int], perm: List[int], perms_list: List[List[int]]):
"""
The idea is similar to nestedForLoops visualized as a recursion tree.
"""
if nums:
for i in range(len(nums)):
# perm.append(nums[i]) mistake, perm will be filled with all nums's elements.
# Method1 perm_copy = copy.deepcopy(perm)
# Method2 add in the parameter list using + (not in place)
# caveat: list.append is in-place , which is useful for operating on global element perms_list
# Note that:
# perms_list pass by reference. shallow copy
# perm + [nums[i]] pass by value instead of reference.
self._permute_recur_agian(nums[:i] + nums[i+1:], perm + [nums[i]], perms_list)
else:
# Arrive at the last loop, i.e. leaf of the recursion tree.
perms_list.append(perm)
if __name__ == "__main__":
array = [random.randint(-10, 10) for _ in range(3)]
sol = Solution()
# perms, time_perm = sol.permute(array, 1)
perms2, time_perm2 = sol.permute(array, 2)
print(perms2)
# print(perms, perms2)
# print(time_perm, time_perm2)
```