數字全排列的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/