如何生成列表的所有排列?例如:
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]
当前回答
用递归求解,遍历元素,取第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个选项,第二项有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。
首先,导入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 permutation(word, first_char=None):
if word == None or len(word) == 0: return []
if len(word) == 1: return [word]
result = []
first_char = word[0]
for sub_word in permutation(word[1:], first_char):
result += insert(first_char, sub_word)
return sorted(result)
def insert(ch, sub_word):
arr = [ch + sub_word]
for i in range(len(sub_word)):
arr.append(sub_word[i:] + ch + sub_word[:i])
return arr
assert permutation(None) == []
assert permutation('') == []
assert permutation('1') == ['1']
assert permutation('12') == ['12', '21']
print permutation('abc')
输出:['abc','acb','bac','bca','cab','cba']
from __future__ import print_function
def perm(n):
p = []
for i in range(0,n+1):
p.append(i)
while True:
for i in range(1,n+1):
print(p[i], end=' ')
print("")
i = n - 1
found = 0
while (not found and i>0):
if p[i]<p[i+1]:
found = 1
else:
i = i - 1
k = n
while p[i]>p[k]:
k = k - 1
aux = p[i]
p[i] = p[k]
p[k] = aux
for j in range(1,(n-i)/2+1):
aux = p[i+j]
p[i+j] = p[n-j+1]
p[n-j+1] = aux
if not found:
break
perm(5)
def permuteArray (arr):
arraySize = len(arr)
permutedList = []
if arraySize == 1:
return [arr]
i = 0
for item in arr:
for elem in permuteArray(arr[:i] + arr[i + 1:]):
permutedList.append([item] + elem)
i = i + 1
return permutedList
我不打算在一个新的行中穷尽所有的可能性,以使它有点独特。