数字全排列的python算法实现

刘光然

【摘  要】在学习算法刷题过程中，很多人选择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/