全排列
给定一个数字列表，返回其所有可能的排列。
样例
给出一个列表[1,2,3]，其全排列为：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
递归代码
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permute(self, nums):
allResult = []
result = []
self.permutes(nums, result, allResult)
return allResult
def permutes(self, nums, result, allResult):
# write your code here
if nums == []:
new_list = []
for i in result:
new_list.append(i)
allResult.append(new_list)
for num in nums:
result.append(num)
new_nums = []
for x in nums:
if x!=num:
new_nums.append(x)
self.permutes(new_nums, result, allResult)
result.pop()
return
非递归代码（仅用于数字不重复的全排列问题中，后来改进）
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permute(self, nums):
nums_used = [0]*len(nums)
nums_used_in_stack = [[] for j in range(len(nums))]
stack = []
allResult = []
while(True):
for key, num in enumerate(nums):
if(nums_used[key] == 0):
if num not in nums_used_in_stack[len(stack)]:
stack.append(num)
nums_used[key] = 1
nums_used_in_stack[len(stack) - 1].append(num)
try:
nums_used_in_stack[len(stack)] = []
except IndexError:
pass
if(len(stack) == len(nums)):
result = []
for i in stack:
result.append(i)
allResult.append(result)
while (True):
try:
x = stack.pop()
except IndexError:
return allResult
for key2, num2 in enumerate(nums):
if num2 == x:
nums_used[key2] = 0
flag = 0
for key3, num3 in enumerate(nums):
if nums_used[key3] == 0 and num3 not in nums_used_in_stack[len(stack)]:
flag = 1
break
else:
flag = 0
if(flag == 0):
continue
else:
break
附上题目来源：
https://www.lintcode.com/problem/kth-largest-element/description
带重复元素的排列
给出一个具有重复数字的列表，找出列表所有不同的排列。
样例
给出一个列表[1,2,2]，其全排列为：
[
[1,2,2],
[2,1,2],
[2,2,1]
]
挑战
使用递归和非递归分别来完成该题。
递归代码
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permuteUnique(self, nums):
allResult = []
result = []
self.permutes(nums, result, allResult)
return allResult
def permutes(self, nums, result, allResult):
# write your code here
nums_used = []
if nums == []:
new_list = []
for i in result:
new_list.append(i)
allResult.append(new_list)
for index in range(0, len(nums)):
if nums[index] not in nums_used:
result.append(nums[index])
nums_used.append(nums[index])
new_nums = []
for x in nums:
new_nums.append(x)
del new_nums[index]
self.permutes(new_nums, result, allResult)
result.pop()
return
非递归代码(改进之后，可用于数字重复或不重复的全排列问题中)
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permuteUnique(self, nums):
nums_used = [0]*len(nums)
nums_used_in_stack = [[] for j in range(len(nums))]
stack = []
allResult = []
while(True):
for key, num in enumerate(nums):
if(nums_used[key] == 0):
if num not in nums_used_in_stack[len(stack)]:
stack.append([key, num])
nums_used[key] = 1
nums_used_in_stack[len(stack) - 1].append(num)
try:
nums_used_in_stack[len(stack)] = []
except IndexError:
pass
if(len(stack) == len(nums)):
result = []
for i in stack:
result.append(i[1])
allResult.append(result)
while (True):
try:
x = stack.pop()[0]
except IndexError:
return allResult
for key2, num2 in enumerate(nums):
if key2 == x:
nums_used[key2] = 0
flag = 0
for key3, num3 in enumerate(nums):
if nums_used[key3] == 0 and num3 not in nums_used_in_stack[len(stack)]:
flag = 1
break
else:
flag = 0
if(flag == 0):
continue
else:
break
附上题目来源：
https://www.lintcode.com/problem/permutations-ii/description
