如何生成列表的所有排列?例如:
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]
当前回答
另一种方法(无libs)
def permutation(input):
if len(input) == 1:
return input if isinstance(input, list) else [input]
result = []
for i in range(len(input)):
first = input[i]
rest = input[:i] + input[i + 1:]
rest_permutation = permutation(rest)
for p in rest_permutation:
result.append(first + p)
return result
输入可以是字符串或列表
print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
其他回答
用递归求解,遍历元素,取第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
功能性风格
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]]
我看到在这些递归函数中进行了很多迭代,而不是纯粹的递归。。。
所以对于那些连一个循环都不能遵守的人来说,这里有一个粗略的、完全不必要的完全递归的解决方案
def all_insert(x, e, i=0):
return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []
def for_each(X, e):
return all_insert(X[0], e) + for_each(X[1:],e) if X else []
def permute(x):
return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])
perms = permute([1,2,3])
在我看来,一个很明显的方式可能是:
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 permutations(head, tail=''):
if len(head) == 0:
print(tail)
else:
for i in range(len(head)):
permutations(head[:i] + head[i+1:], tail + head[i])
称为:
permutations('abc')