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

栏目: IT技术 · 发布时间: 4年前

内容简介:本文始发于个人公众号:

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

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

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

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

回溯法

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

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

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

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

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

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

所以我们把之前八皇后的代码拿过来稍作修改即可,为了放置一个皇后重复放置在多个位置,我们需要存储皇后的状态,即有没有放置过。一般竞赛当中这种标记的变量称为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当中的逻辑,这个代码其实只有几行:

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

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

最后我们来看下代码,如果你不懂怎么算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难度 ,并且题目的题意还是之前见过的,主要是给大家加深一下回溯算法的映像用的,没什么太多的新内容。

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

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

风云Flash ActionScript高级编程艺术

风云Flash ActionScript高级编程艺术

赵英杰 / 第1版 (2006年7月1日) / 2006-7 / 45.00元

本书从基本的Actionscript语言概念开始介绍,配以实际的程序实例并穿插生动的图示说明,深入浅出地讲解Flash ActionScript程序的运用逻辑与概念,让读者从实例中学习进而融会贯通。同时,本书也说明面向对象程序设计(00P)的语法及常用类别实例,提升读者制作F1ash作品的造诣和能力。全书共分为10章,精彩实例包括以三角函数制作的抽奖轮盘,FlashLite手机版孔明棋游戏,Bit......一起来看看 《风云Flash ActionScript高级编程艺术》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具