劉光然

【摘? 要】在學習算法刷題過程中，很多人選擇leetcode這個平臺來進行。本文對leetcode平臺第46題全排列[1]進行了詳細分析，并對[2]中給出的代碼做了優(yōu)化，最后用一行python代碼實現(xiàn)了全排列功能。

【關(guān)鍵詞】全排列; leetcode;python

引言

在美國互聯(lián)網(wǎng)發(fā)展的過程中，美國企業(yè)面對著招聘需求增長，采用了寫題為主的面試方法論。時至今日，像Google、FaceBook、Amazon等公司，依然保留和沿用著以寫題為主的面試方法。于是，就有了Leetcode和中文版的Leetcode。

本文對Leetcode第46題全排列[1]進行了詳細的分析，并給出了一行python改進解法。

1.Leetcode第46題內(nèi)容介紹

46題：給定一個沒有重復數(shù)字的序列，返回其所有可能的全排列。

示例： 輸入： [1，2，3]

輸出： [ [1，2，3]， [1，3，2]， [2，1，3]， [2，3，1]， [3，1，2]， [3，2，1] ]

1.1題目分析

看完題目，以及給出的示例輸入輸出，可以發(fā)現(xiàn)這就是一個普通的全排列問題，輸入一個整型的數(shù)組，輸出是一個數(shù)組，同時數(shù)組中的每一個元素就是一個排列。

1.2解題思路

參考文獻[3]和[4]，“回溯”算法也叫“回溯搜索”算法， “回溯”指的是“狀態(tài)重置”，可以理解為“回到過去”、“恢復現(xiàn)場”，是在編碼的過程中，是為了節(jié)約空間而使用的一種技巧。而回溯其實是“深度優(yōu)先遍歷”特有的一種現(xiàn)象。 “全排列”就是一個非常經(jīng)典的“回溯”算法的應用。我們知道，N 個數(shù)字的全排列一共有 N！ 這么多個。

“全排列”問題的樹形結(jié)構(gòu)如下所示：

使用編程的方法得到全排列，就是在這樣的一個樹形結(jié)構(gòu)中進行編程，具體來說，就是執(zhí)行一次深度優(yōu)先遍歷，從樹的根結(jié)點到葉子結(jié)點形成的路 就是一個全排列。

2.編碼步驟：

（1）首先這棵樹除了根結(jié)點和葉子結(jié)點以外，每一個結(jié)點做的事情其實是一樣的，即在已經(jīng)選了一些數(shù)的前提，我們需要在剩下還沒有選擇的數(shù)中按照順序依次選擇一個數(shù);

（2）遞歸的終止條件是，數(shù)已經(jīng)選夠了，因此我們需要一個變量來表示當前遞歸到第幾層，我們把這個變量叫做 depth;

（3）這些結(jié)點實際上表示了搜索（查找）全排列問題的不同階段，為了區(qū)分這些不同階段，我們就需要一些變量來記錄為了得到一個全排列，程序進行到哪一步了，在這里我們需要兩個變量：

（4）在非葉子結(jié)點處，產(chǎn)生不同的分支，這一操作的語義是：在還未選擇的數(shù)中依次選擇一個元素作為下一個位置的元素，這顯然得通過一個循環(huán)實現(xiàn)。

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中提交的形式，所以這個代碼在普通的環(huán)境中是無法執(zhí)行的。

4.小結(jié)

本文用一行python代碼實現(xiàn)了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/