[LintCode 15] Permutations
Description
Given a list of numbers, return all possible permutations.
给定一个数字列表,返回其所有可能的排列。
https://www.lintcode.com/problem/permutations/description?_from=ladder&&fromId=1
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Note
对于求全排列问题,从所有选择中挑选一个数/物品,接着在剩下的物品中再挑选,并且有顺序区分,所以需要在每次选择时都重复当时所有的选择,并进行递归。
递归的定义:找到所有permutation开头的排列,加到results里。
Update Review
Code
Python3 on LintCode
PS: 代码中有一个语法上需要注意的问题:
results.append(current_premute[:]),这一写法很重要,即复制一个全新的current_premute加进结果中,如果单纯的写为results.append(current_premute[]),那么在执行完递归后result的结果将加入的全部是current_premute初始值空数组,原因是递归的时候变量都保存在栈里,result里面append的是current_premute的地址。但是,当递归函数运行结束,current_premute就被pop掉了。所以每次添加函数内变量时需要传值调用,而不是传址调用。
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permute(self, nums):
# write your code here
if not nums or len(nums) == 0:
return [[]]
results = []
current_premute = []
self.dfs(nums, current_premute, results)
return results
def dfs(self, nums, current_premute, results):
if len(current_premute) == len(nums):
results.append(current_premute[:])
for num in nums:
if self.is_valid(num, current_premute):
current_premute.append(num)
self.dfs(nums, current_premute, results)
current_premute.pop()
def is_valid(self, num, current_premute):
for item in current_premute:
if item == num:
return False
return True
Ref Code
本参考程序来自九章算法,由 @令狐冲 提供
Given a collection of 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], and [3,2,1].
class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
# write your code here
def _permute(result, temp, nums):
if nums == []:
result += [temp]
else:
for i in range(len(nums)):
_permute(result, temp + [nums[i]], nums[:i] + nums[i+1:])
if nums is None:
return []
if nums is []:
return [[]]
result = []
_permute(result, [], sorted(nums))
return result
# Non-Recursion
class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
if nums is None:
return []
if nums == []:
return [[]]
nums = sorted(nums)
permutation = []
stack = [-1]
permutations = []
while len(stack):
index = stack.pop()
index += 1
while index < len(nums):
if nums[index] not in permutation:
break
index += 1
else:
if len(permutation):
permutation.pop()
continue
stack.append(index)
stack.append(-1)
permutation.append(nums[index])
if len(permutation) == len(nums):
permutations.append(list(permutation))
return permutations
This blog is under a CC BY-NC-SA 3.0 Unported License
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享(BY-NC-SA):使用者可以对本创作进行共享、演绎,但使用时须进行署名(同时标明是否(对原始作品)作了修改),且不得运用于商业目的,采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。
本文链接:https://dataleoz.com/lintcode-permutations/