如何生成列表的所有排列?例如:
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]
当前回答
我看到在这些递归函数中进行了很多迭代,而不是纯粹的递归。。。
所以对于那些连一个循环都不能遵守的人来说,这里有一个粗略的、完全不必要的完全递归的解决方案
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])
其他回答
另一种方法(无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']))
如果不想使用内置方法,例如:
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'}
这是受Haskell实现使用列表理解的启发:
def permutation(list):
if len(list) == 0:
return [[]]
else:
return [[x] + ys for x in list for ys in permutation(delete(list, x))]
def delete(list, item):
lc = list[:]
lc.remove(item)
return lc
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]
]
如果用户希望在列表中保留所有排列,可以使用以下代码:
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)