如何生成列表的所有排列?例如:
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]
当前回答
对于Python 2.6及以上版本:
import itertools
itertools.permutations([1, 2, 3])
这将作为生成器返回。使用列表(排列(xs))作为列表返回。
其他回答
该算法是最有效的算法,它避免了递归调用中的数组传递和操作,适用于Python 2、3:
def permute(items):
length = len(items)
def inner(ix=[]):
do_yield = len(ix) == length - 1
for i in range(0, length):
if i in ix: #avoid duplicates
continue
if do_yield:
yield tuple([items[y] for y in ix + [i]])
else:
for p in inner(ix + [i]):
yield p
return inner()
用法:
for p in permute((1,2,3)):
print(p)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
首先,导入itertools:
import itertools
排列(顺序重要):
print(list(itertools.permutations([1,2,3,4], 2)))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]
组合(顺序无关紧要):
print(list(itertools.combinations('123', 2)))
[('1', '2'), ('1', '3'), ('2', '3')]
笛卡尔积(具有多个可迭代项):
print(list(itertools.product([1,2,3], [4,5,6])))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]
笛卡尔积(具有一个可迭代的和自身):
print(list(itertools.product([1,2], repeat=3)))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
常规实现(无收益-将在内存中完成所有操作):
def getPermutations(array):
if len(array) == 1:
return [array]
permutations = []
for i in range(len(array)):
# get all perm's of subarray w/o current item
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
permutations.append([array[i], *p])
return permutations
产量实施:
def getPermutations(array):
if len(array) == 1:
yield array
else:
for i in range(len(array)):
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
yield [array[i], *p]
基本思想是在第一个位置遍历数组中的所有元素,然后在第二个位置遍历所有其他元素,而没有为第一个位置选择的元素,等等。您可以使用递归来实现这一点,其中停止条件是到达一个由1个元素组成的数组,在这种情况下,您返回该数组。
生成所有可能的排列
我正在使用python3.4:
def calcperm(arr, size):
result = set([()])
for dummy_idx in range(size):
temp = set()
for dummy_lst in result:
for dummy_outcome in arr:
if dummy_outcome not in dummy_lst:
new_seq = list(dummy_lst)
new_seq.append(dummy_outcome)
temp.add(tuple(new_seq))
result = temp
return result
测试用例:
lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)
用递归求解,遍历元素,取第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