16

LeetCode46 回溯算法求全排列，这次是真全排列

 4 years ago
source link: http://www.cnblogs.com/techflow/p/12636563.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

本文始发于个人公众号： TechFlow ，原创不易，求个关注

今天是 LeetCode的26篇 文章，我们来实战一下全排列问题。

在之前的文章当中，我们讲过八皇后、回溯法，也提到了 全排列 ，但是毕竟没有真正写过。今天的LeetCode46题正是让我们生成给定元素的全排列。

题意很简单，只有一句话，给定一个没有重复元素的序列，让我们返回这个序列所有的全排列，并且我们不需要考虑这些排列的顺序。

回溯法

我们在之前的文章当中分析过，全排列问题，可以看成是 搜索问题 ，从而近似成八皇后问题。在八皇后问题当中，我们枚举的是棋盘的每一行当中的皇后放置的位置，而全排列其实也一样，我们要枚举每一个元素放置的位置。不过八皇后当中要求皇后除了不能同行同列之外还不能同对角线，而我们排列元素可以 忽略这个要求 。也就是说我们把每一行皇后放置的列号看成是每个元素摆放的位置，并且忽略同对角线的限制的话，那么八皇后问题和全排列问题就完全一样了。

如果还不理解，可以参考一下下图，我们给皇后编号，把皇后同样看成是序列当中的元素，那么八皇后的摆放位置刚好可以映射成一种排列。映射的方式非常简单，就是我们忽略行的信息，依次记录下皇后摆放的列号。

VB7NNvz.jpg!web

如果你能想通这两个看似完全不同的问题当中的相似之处，说明你对搜索问题的理解已经有些入门了。

思路清楚了，总之我们要 枚举皇后摆放的状态 。你可以按顺序遍历位置，然后枚举各个位置上放置的皇后，也可以顺序遍历皇后，枚举当前皇后可以放置的位置。两者是等价的，你可以根据自己的理解进行操作。

一般来说我喜欢遍历位置，枚举皇后。因为会引起冲突的是皇后，而不是位置。我们往往要判断皇后之间的关系以及皇后的状态，所以我们 枚举皇后会比较贴合思路 。

所以我们把之前八皇后的代码拿过来稍作修改即可，为了放置一个皇后重复放置在多个位置，我们需要存储皇后的状态，即有没有放置过。一般竞赛当中这种标记的变量称为flag，如果标记多个那就是flag数组。更多细节我们来看代码：

class Solution:
    def dfs(self, nums, n, i, cur, ret, flag):
        if i == n:
            ret.append(cur.copy())
            return
        for p in range(n):
            # 遍历所有元素
            # 如果p元素已经放置过了，跳过
            if flag[p]:
                continue
            # 当前位置放置p
            cur.append(nums[p])
            # flag[p]置为True
            flag[p] = True
            # 递归
            self.dfs(nums, n, i+1, cur, ret, flag)
            # 回溯
            cur.pop()
            flag[p] = False
        
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 记录元素i有没有放置过
        flag = [False for _ in range(n)]
        self.dfs(nums, n, 0, [], ret, flag)
        return ret

代码很短，细节也不多，只要理解了我们是按照顺序遍历位置，然后对于每一个位置遍历可以放置的元素，然后递归回溯即可。基本上可以说是模板题，如果理解有难度的话，可以看一下之前详解八皇后问题的文章：

LeetCode 31：递归、回溯、八皇后、全排列一篇文章全讲清楚

其他方法

回溯法是这个问题的标准解法，那么这题还有没有其他方法呢？

其实是有的，也不难，在LeetCode31题的文章，也就是上面那个链接的文章当中我们解决了一个叫做 下一个排列 的问题。在这道题当中，我们给定一个序列，要求返回在它所有的全排列当中刚好字典序比它大1的排列，这个方法称为next_permutation。

关于next_permutation的计算方法 也在链接里 ，如果有忘记的或者是最近关注的可以点下链接回顾一下，计算方法是完全一样的，我就不再重复了。

LeetCode 31：递归、回溯、八皇后、全排列一篇文章全讲清楚

如果还记得这道题的话就好办了，我们使用它很容易解出当前的问题。因为我们只需要获得给定序列的最小排列，然后不停地调用这个方法就好了，直到没有更大的序列退出即可。 从最小的序列一直获取到最大的，当然就是全排列了。

在LeetCode31题当中，这是一个inplace的方法，没有返回值。并且当序列达到最大的时候，会自动再从最小的开始。我们需要稍稍修改一下，加上一个返回值， 表示当前的序列是否是最大的 。如果序列达到最大，说明我们可以不用继续往下寻找了，我们return一个True，表示可以退出了，否则我们return False，表示还有其他结果。

本质上我们是从最小的排列开始，不停地用一个叫做get_next的方法获取比当前序列大的下一个序列，当没有更大的序列的时候，说明我们已经获得了所有的排列，那么直接返回结果即可。如果忽略get_next当中的逻辑，这个代码其实只有几行：

MfQvQfr.png!web

其实这是一个取巧的办法，利用之前的思路我们完全不用思考，几乎可以无脑得到答案。但是从另外一个角度来说，这也是算法的魅力，毕竟通往终点的路往往不止一条。

最后我们来看下代码，如果你不懂怎么算next_permutation光看注释是很难看懂的，划到上面的链接看看吧。

class Solution:
    def get_next(self, nums: List[int]):
        """
        Do not return anything, modify nums in-place instead.
        """
        # 长度
        n = len(nums)
        # 记录图中i-1的位置
        pos = n - 1
        for i in range(n-1, 0, -1):
            # 如果降序破坏，说明找到了i
            if nums[i] > nums[i-1]:
                pos = i-1
                break
                
        for i in range(n-1, pos, -1):
            # 从最后开始找大于pos位置的
            if nums[i] > nums[pos]:
                # 先交换元素，在进行翻转
                nums[i], nums[pos] = nums[pos], nums[i]
                # 翻转[pos+1, n]区间
                nums[pos+1:] = nums[n:pos:-1]
                return False
        return True
        
        
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        # 从小到大排序，获得最小排列
        nums = sorted(nums)
        ret.append(nums.copy())
        # 如果还有下一个排列则继续调用
        while not self.get_next(nums):
            # 要.copy()是因为Python中存储的引用，如果不加copy
            # 会导致当nums发生变化之后，ret中存储的数据也会变化
            ret.append(nums.copy())
        return ret

今天的问题并不难，只是 Medium难度 ，并且题目的题意还是之前见过的，主要是给大家加深一下回溯算法的映像用的，没什么太多的新内容。

文章的内容就是这些，如果觉得有所收获，请顺手点个 关注或者转发 吧，你们的举手之劳对我来说很重要。

JzEJVfa.png!web


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK