Given a collection of distinct numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
运用递归。 1234为例子
for i in 1234:
1 + 234(的全排列)
2 + 134（的全排列）
3 + 124（的全排列）
4 + 123 （的全排列）
对应程序的17行
class Solution(object):
def __init__(self):
self.res = [] def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.help(nums, 0, len(nums)) return self.res def help(self, a, lo, hi):
if(lo == hi):
self.res.append(a[0:hi])
for i in range(lo, hi):
self.swap(a, i, lo)
self.help(a, lo + 1, hi)
self.swap(a, i, lo)
def swap(self, a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
非递归
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums = sorted(nums.copy())
res = [nums.copy()]
n = self.next_permute(nums)
while True:
if n is None:
break
res.append(n)
n = self.next_permute(n.copy())
return res
def next_permute(self, a):
i = -1
for index in range(0, len(a) - 1)[::-1]:
if(a[index] < a[index + 1]):
i = index
break
if i==-1:
return None
min_i = a.index(min([k for k in a[i+1:] if k >a[i]]))
self.swap(a, i, min_i)
an = a[:i + 1] + self.revers(a[i + 1:])
return an
def revers(self, x):
for i in range(int(len(x) / 2)):
temp = x[i]
x[i] = x[len(x) - i - 1]
x[len(x) - i - 1] = temp
return x
def swap(self, a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp