[LintCode 15] Permutations

Author Avatar
DataLeoZ 6月 19, 2019
  • 在其它设备中阅读本文章

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/