如何生成列表的所有排列?例如:
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。
其他回答
使用计数器
from collections import Counter
def permutations(nums):
ans = [[]]
cache = Counter(nums)
for idx, x in enumerate(nums):
result = []
for items in ans:
cache1 = Counter(items)
for id, n in enumerate(nums):
if cache[n] != cache1[n] and items + [n] not in result:
result.append(items + [n])
ans = result
return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
如果用户希望在列表中保留所有排列,可以使用以下代码:
def get_permutations(nums, p_list=[], temp_items=[]):
if not nums:
return
elif len(nums) == 1:
new_items = temp_items+[nums[0]]
p_list.append(new_items)
return
else:
for i in range(len(nums)):
temp_nums = nums[:i]+nums[i+1:]
new_temp_items = temp_items + [nums[i]]
get_permutations(temp_nums, p_list, new_temp_items)
nums = [1,2,3]
p_list = []
get_permutations(nums, p_list)
此解决方案实现了一个生成器,以避免在内存中保留所有排列:
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
用递归求解,遍历元素,取第i个元素,然后问自己:“其余项目的排列是什么”,直到没有更多的元素。
我在这里解释了解决方案:https://www.youtube.com/watch?v=_7GE7psS2b4
class Solution:
def permute(self,nums:List[int])->List[List[int]]:
res=[]
def dfs(nums,path):
if len(nums)==0:
res.append(path)
for i in range(len(nums)):
dfs(nums[:i]+nums[i+1:],path+[nums[i]])
dfs(nums,[])
return res
注意,该算法具有n个阶乘时间复杂度,其中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]