如何生成列表的所有排列?例如:
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]
当前回答
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)
```
其他回答
如果不想使用内置方法,例如:
import itertools
list(itertools.permutations([1, 2, 3]))
你可以自己实现permute函数
from collections.abc import Iterable
def permute(iterable: Iterable[str]) -> set[str]:
perms = set()
if len(iterable) == 1:
return {*iterable}
for index, char in enumerate(iterable):
perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])
return perms
if __name__ == '__main__':
print(permute('abc'))
# {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
print(permute(['1', '2', '3']))
# {'123', '312', '132', '321', '213', '231'}
对于Python 2.6及以上版本:
import itertools
itertools.permutations([1, 2, 3])
这将作为生成器返回。使用列表(排列(xs))作为列表返回。
另一种解决方案:
def permutation(flag, k =1 ):
N = len(flag)
for i in xrange(0, N):
if flag[i] != 0:
continue
flag[i] = k
if k == N:
print flag
permutation(flag, k+1)
flag[i] = 0
permutation([0, 0, 0])
使用标准库中的itertools.permutations:
import itertools
list(itertools.permutations([1, 2, 3]))
从这里改编的是itertools.permutations如何实现的演示:
def permutations(elements):
if len(elements) <= 1:
yield elements
return
for perm in permutations(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)
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]
]