论文部分内容阅读
【摘 要】在学习算法刷题过程中，很多人选择leetcode这个平台来进行。本文对leetcode平台第46题全排列[1]进行了详细分析，并对[2]中给出的代码做了优化，最后用一行python代码实现了全排列功能。
【关键词】全排列; leetcode;python
引言
在美国互联网发展的过程中，美国企业面对着招聘需求增长，采用了写题为主的面试方法论。时至今日，像Google、FaceBook、Amazon等公司，依然保留和沿用着以写题为主的面试方法。于是，就有了Leetcode和中文版的Leetcode。
本文对Leetcode第46题全排列[1]进行了详细的分析，并给出了一行python改进解法。
1.Leetcode第46题内容介绍
46题：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例： 输入： [1，2，3]
输出： [ [1，2，3]， [1，3，2]， [2，1，3]， [2，3，1]， [3，1，2]， [3，2，1] ]
1.1题目分析
看完题目，以及给出的示例输入输出，可以发现这就是一个普通的全排列问题，输入一个整型的数组，输出是一个数组，同时数组中的每一个元素就是一个排列。
1.2解题思路
参考文献[3]和[4]，“回溯”算法也叫“回溯搜索”算法， “回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。 “全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N！ 这么多个。
“全排列”问题的树形结构如下所示：
使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路 就是一个全排列。
2.编码步骤：
（1）首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即在已经选了一些数的前提，我们需要在剩下还没有选择的数中按照顺序依次选择一个数;
（2）递归的终止条件是，数已经选够了，因此我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth;
（3）这些结点实际上表示了搜索（查找）全排列问题的不同阶段，为了区分这些不同阶段，我们就需要一些变量来记录为了得到一个全排列，程序进行到哪一步了，在这里我们需要两个变量：
（4）在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
3.代码的编写
由于编写代码采用的python语言，可以充分利用python的精简的风格和特殊的语法糖，直接给出一行python代码如下：
class Solution：
def permute（self， nums： List[int]） -> List[List[int]]：
return [ p[：i] + [nums[0]] + p[i：]
for i in range（len（nums））
for p in self.permute（nums[1：]）
] or [[]]
該代码对文献[2]中的代码进行了简化，是本文的一个精简的改进。
由于是Leetcode中提交的形式，所以这个代码在普通的环境中是无法执行的。
4.小结
本文用一行python代码实现了leetcode46题全排列，并且对文献[2]的代码进行了精简的改进。
参考文献
[1] https：//leetcode-cn.com/problems/permutations/
[2] https：//leetcode.com/problems/permutations/discuss/18241/One-Liners-in-Python
[3] 胡松涛。 图解LeetCode初级算法（Python版）. 北京：清华大学出版社，2020.
[4]https：//leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
【关键词】全排列; leetcode;python
引言
在美国互联网发展的过程中，美国企业面对着招聘需求增长，采用了写题为主的面试方法论。时至今日，像Google、FaceBook、Amazon等公司，依然保留和沿用着以写题为主的面试方法。于是，就有了Leetcode和中文版的Leetcode。
本文对Leetcode第46题全排列[1]进行了详细的分析，并给出了一行python改进解法。
1.Leetcode第46题内容介绍
46题：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例： 输入： [1，2，3]
输出： [ [1，2，3]， [1，3，2]， [2，1，3]， [2，3，1]， [3，1，2]， [3，2，1] ]
1.1题目分析
看完题目，以及给出的示例输入输出，可以发现这就是一个普通的全排列问题，输入一个整型的数组，输出是一个数组，同时数组中的每一个元素就是一个排列。
1.2解题思路
参考文献[3]和[4]，“回溯”算法也叫“回溯搜索”算法， “回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。 “全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N！ 这么多个。
“全排列”问题的树形结构如下所示：
使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路 就是一个全排列。
2.编码步骤：
（1）首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即在已经选了一些数的前提，我们需要在剩下还没有选择的数中按照顺序依次选择一个数;
（2）递归的终止条件是，数已经选够了，因此我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth;
（3）这些结点实际上表示了搜索（查找）全排列问题的不同阶段，为了区分这些不同阶段，我们就需要一些变量来记录为了得到一个全排列，程序进行到哪一步了，在这里我们需要两个变量：
（4）在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
3.代码的编写
由于编写代码采用的python语言，可以充分利用python的精简的风格和特殊的语法糖，直接给出一行python代码如下：
class Solution：
def permute（self， nums： List[int]） -> List[List[int]]：
return [ p[：i] + [nums[0]] + p[i：]
for i in range（len（nums））
for p in self.permute（nums[1：]）
] or [[]]
該代码对文献[2]中的代码进行了简化，是本文的一个精简的改进。
由于是Leetcode中提交的形式，所以这个代码在普通的环境中是无法执行的。
4.小结
本文用一行python代码实现了leetcode46题全排列，并且对文献[2]的代码进行了精简的改进。
参考文献
[1] https：//leetcode-cn.com/problems/permutations/
[2] https：//leetcode.com/problems/permutations/discuss/18241/One-Liners-in-Python
[3] 胡松涛。 图解LeetCode初级算法（Python版）. 北京：清华大学出版社，2020.
[4]https：//leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/