今天我們講的是LeetCode的31題，這是一道非常經典的問題，經常會在面試當中遇到。在今天的文章當中除了關於題目的分析和解答之外，我們還會詳細解讀深度優先搜索和回溯算法，感興趣的同學不容錯過。
標題
Next Permutation
難度
Medium
描述
實現C++當中經典的庫函數next permutation，即下一個排列。如果把數組當中的元素看成字典序的話，那下一個排列即是字典序比當前增加1的排列。如果已經是字典序最大的情況，則返回字典序最小的情況，即從頭開始。
Implement next permutation , which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be [in-place](http://en.wikipedia.org/wiki/In- place_algorithm) and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
樣例
1,2,3 -> 1,3,2
3,2,1 -> 1,2,3
1,1,5 -> 1,5,1
介紹和分析
如果對C++不夠熟悉的同學可能不知道next permutation這個庫函數，這個庫函數可以生成下一個字典序的排列。
舉個例子，比如樣例當中1 2 3這三個元素，我們把它所有的排列列舉出來，一共是6種：
<code>1 2 31 3 22 1 32 3 13 1 23 2 1/<code>
這6種排列的字典序依次增加，而next permutation呢則是根據當前的排列返回下一個排列。比如我們輸入1 2 3，返回1 3 2，我們輸入3 1 2，返回3 2 1。而如果我們輸入字典序最大的，也就是3 2 1時，則從頭開始，返回字典序最小的1 2 3.
暴力
老規矩，我們第一優先級思考最簡單的暴力解法。
最簡單粗暴的方法是什麼，當然是將所有的排列全部列舉出來，然後根據字典順序排序，最後返回答案。
說起來很簡單，但是實現的話一點都不容易。首先，我們怎麼獲取所有的排列呢？這個問題最簡單的方法是通過遞歸實現深度優先搜索。我單單這麼說，對搜索算法不夠熟悉的同學可能理解不了。沒關係，我們一步一步來推導。我們先把原問題放一放，來看一道經典的搜索問題：八皇后問題。
八皇后問題
八皇后問題是假設我們有一張8*8的國際象棋的棋盤，我們要在棋盤上放置八個皇后，使得這些皇后之間彼此相安無事。
眾所周知，在國際象棋當中皇后比較牛X，可以橫豎以及對角線斜著走。也就是說如果將兩個皇后放在同行或者同列以及同對角線，那麼就會出現皇后之間互相攻擊的情況，也就不滿足題目要求了。
這個問題我們顯然不考慮無腦的暴力枚舉，即使我們知道是8個皇后，如果我們真的用8重循環去查找合法位置的話，那麼一定會複雜度爆炸計算到天荒地老的。原因也很簡單，我們稍微分析一下複雜度就能知道。對於每重循環，我們都需要遍歷64個位置，那麼一共的複雜度就是64^8，這是一個非常龐大的數字，幾乎是算不完的。而且如果我們變換一下題目，假設我們一開始不知道皇后的數量，變成n皇后問題，那麼我們連寫幾重循環都不知道。
解決這個問題的方法需要我們人為地將問題的規模縮小，其實我們沒有必要去遍歷所有的位置。因為根據題目條件，皇后不能同行，所以我們每行只能放置一個皇后。而剛好我們是8*8的棋盤，所以我們剛好是每行和每列都只能放置一個皇后。也就是說，我們一行一行地放置皇后。
所以解法就變成了，對於第1行而言，我們有8個位置可以放置皇后。我們隨意地選擇了一個位置之後，只剩下了7個位置給第二行，然後再放一個，再剩下6個位置給第三行……以此類推，當這樣所有皇后放置完了，我們檢查完合法性之後，我們接下來需要回到之前的行，選擇其他的位置。
舉個簡單的例子，假設我們一開始的放置方案是[1, 2, 3, 4, 5, 6, 7, 8]。
我們是放置完第8行的棋子之後進入的結束狀態，由於第八行只剩下了一個位置，所以沒有其他可以選擇的情況。在這種情況下，我們應該往上回顧，回到第7行的時候，對於第7行來說可以選擇的位置有[7, 8]，第一次我們選擇了7，那麼我們可以試試選擇8，這樣就可以得到新的答案[1, 2, 3, 4, 5, 6, 8, 7]。
這樣又結束了之後，我們再回顧的時候發現第7行的情況也都選擇完了，那麼要繼續往上，回顧第6行的情況。如果我們把搜索樹畫一部分出來的話是這樣：
你會發現我們一行一行放置的過程在樹上對應的是一層一層往下的過程，而我們枚舉完了之後回顧之前的行的時候，體現在搜索樹上是反向的逆流而上的過程。我們把枚舉完了後續回到之前的決策的算法稱為“回溯法”，想象一下一棵從源頭展開的搜索樹，我們順著它一層一層往下遍歷，遍歷結束完了之後又逆流而上去修改之前的決策，再拓展新的搜索空間。
這也有點像是平行時空，根據平行時空理論，世界上的每一個隨機決定都會生成一個平行宇宙，如果你有穿梭時間的能力，那麼你就可以回到之前產生平行時空的節點，去遍歷其他的平行時空。如果你看過經典的懸疑電影蝴蝶效應的話，那麼你一定知道我在說什麼。
關於回溯這個概念，我也在之前講解棧和模擬遞歸的文章當中提到過，感興趣的同學可以點擊下方的鏈接查看。
模板代碼
如果是初學者，即使是理解了遞歸的概念想要自己寫出代碼來也是一件不容易的事情。因為在我們看來記錄所有節點的狀態，遍歷，再回到之前的狀態，再繼續搜索，這是一個非常複雜的過程。
好在我們並不需要自己記錄這個過程，因為計算機在執行程序的時候會有一個稱為方法棧的東西，記錄我們執行的所有函數和方法的狀態。比如我們在A程序中執行了B程序的代碼，like this:
我們在A當中的第二行執行了B這個函數，那麼系統會為我們記錄下我們在執行B的時候的位置是第二行，當B執行結束，還會回到調用的位置，繼續往下執行。而遞歸呢，則是利用這一特性，讓A來執行自己：
和剛才一樣，系統同樣會為我們記錄執行A的位置。A執行了A，在我們看來是一樣的，但是系統會儲存兩份方法狀態，我們可以簡單認為後面執行的A是A1，那麼當A1執行結束之後，又會回到A執行A1的位置。而用遞歸來實現搜索呢，只是在此基礎上加上了一點循環而已。
這就是一個簡單的搜索的代碼框架了，我們遍歷每個節點的所有決策，然後記錄下這個選擇，進行往下遞歸。當我們執行完再次回到這個位置這一行代碼的時候，我們已經遍歷完了這個選擇所有的情況，所以我們要撤銷這個選擇帶來的一些影響，好方便枚舉下一個選擇。
但是這樣還沒結束，還有一點小問題，就是我們只需要放置8個皇后，我們需要針對這點做限制，不然就會無窮無盡遞歸下去了。做限制的方法也很簡單，本質上來說我們是要限制遞歸的深度，所以我們可以用一個變量來記錄遞歸的深度，每次往下遞歸的時候就加上1，如果遞歸深度達到了我們的要求，就不再往下遞歸了。
加上深度判斷之後，我們就得到了經典的回溯的代碼框架。幾乎可以說無論什麼樣的回溯搜索問題，都脫離不了這個代碼框架，只是具體執行和撤銷的邏輯有所不同而已：
我們利用這個代碼框架來實現一下八皇后問題，代碼很短，也很好理解
如果我們把八皇后問題當中的不能同列同對角線的判斷去掉，也就是說皇后不能同行，一行只能放一個皇后，我們把數組當中的元素看成是皇后，那麼去掉限制之後的八皇后問題就變成了全排列問題。而這個問題是找出所有的排列當中大於當前這個排列的最小的排列，也就是說我們不需要記錄所有的排列結果，只需要記錄滿足條件的那一個。
那麼套用上面的代碼框架，這個問題立刻迎刃而解。
我們之所以費這麼大勁繞過去講解八皇后問題，就是為了讓大家理解全排列和回溯算法之間的關係。但是如果你真的這麼去解題，你會發現是無法通過的，原因也很簡單，因為全排列是一個n!的算法，它的複雜度非常大。對於一個稍微大一點的n，我們就得不到結果。
貪心
費了這麼大勁獲得了一個不能用的答案，看起來有些可惜，但是其實一點也不浪費。我們是為了學習算法和提升自己來做題的，而不僅僅是為了通過。就好像本文的產生並不僅僅是作為題解產生的，而是希望實實在在地傳遞一些知識和技能，這也是我的初心。
言歸正傳，我們不用分析也知道，超時的原因很簡單，因為我們做了許多無用功。因為我們不論大小，把所有的全排列都求出來了。那麼我們能不能有什麼辦法不用求出所有的全排列就獲得答案呢？
當然是有的，但是要想能夠想到這個答案，需要我們對這個問題有更深一點的理解。
我們可以很容易想到，最小的全排列是升序的，最大的是降序的。那麼中間大小的呢，大概是什麼樣子的？顯然是有升有降，參差不齊的。我們觀察一下相鄰排列的規律，看看能發現什麼。
舉個例子，1 2 3的下一個排列是1 3 2，是交換2和3得到的。我們再來看一個，1 3 2 4的下一個排列是1 3 4 2，也是交換了兩個元素得到的。如果你列舉更多會發現，不論當前的全排列長什麼樣，我們都可以交換其中的兩個元素得到下一個排列。也就是說我們並不需要遍歷所有的全排列，只需要找到兩個合適的元素，將它們交換即可。
根據排列順序遞增的條件，我們可以想明白，我們應該找的這兩個元素應該是小的在前，大的在後，這樣我們將它們交換之後，它們的字典序才會增加。所以到這裡，整個問題就變成了我們該怎麼樣找到這樣的元素呢？
我們可以繼續想出一些條件，比如我們可以想到我們選擇的這兩個元素當中較大的那個應該儘量小，其中小的那個要儘量大，並且這兩個元素的位置要儘量靠後，不然的話我們一交換元素，可能帶來太多的提升。
雖然這些條件看起來比較直觀，但其實很有用，我們只需要將這些想法想辦法加以量化，就可以得到答案了。在此之前，我們先來觀察一下一個可能的通用例子，來尋找一下通用的解法。
這是一個典型的排列的展示圖，橫座標是元素放置的位置，縱座標是元素的大小。這個圖很經典是在於如果我們抽象一些理解，它可以代表所有的排列。不論什麼樣的排列我們都可以認為它由三部分組成，第一部分是序列前端的遞增的部分，第二個部分是中間參差不齊的部分，和最後遞減的部分。對於不同的排列而言，模式都是一樣的，差別只在於這三個部分的長度。
我們對著圖簡單分析一下，可以發現對於後面降序的部分，我們不論怎麼交換都不可能提升字典序，只能降低。對於前面的部分，我們交換元素可以提升字典序，但顯然不是最優的結果。那麼問題就很明顯了，我們應該把關注點放在中間參差不齊的部分。根據我們之前的直觀結論，我們選擇的元素應該儘可能靠後，所以我們的關注點可以進一步地縮小，可以鎖定在第二個部分的末尾，也就是圖中的a[i-1]的位置。
我們選擇a[i-1]的主要原因很簡單，因為它比a[i]要小，而從a[i]開始降序。那麼剩下的問題就更簡單了，我們要做的就是從第三部分選擇一個比a[i-1]大的元素和它交換位置。這個元素怎麼選呢？我們可以簡單地貪心，選擇比它大的最小的那個。由於a[i] > a[i-1]，所以可以確定，這樣的元素一定存在。從圖上來看，這個比a[i-1]但又儘量小的元素就是a[j]。
我們把a[j]和a[i-1]交換了之後得到了一個新的排列，並且這個排列比之前的排列大，也就是說我們提升了字典序。但是這還不是最小的情況。原因也很簡單，因為最後一部分的元素還是降序的，如果我們把它變成升序，它的字典序還會進一步降低。
我們來看一個例子：[1,8, 9, 4, 10, 6, 3]
根據我們之前的結論，我們會將4和6交換，得到：[1, 8, 9, 6, 10, 4, 3]，這個字典序比之前更大，但並不是最小的，我們還可以將最後的10，4，3進行翻轉，變成3，4，10。這樣最終的答案是: [1, 8, 9, 4, 3, 6, 10]
我們分析一下可以發現，我們交換了兩個元素的位置之後，並沒有影響數組第三部分的元素是降序的這個特性。所以我們並不需要額外的處理，直接翻轉數組就可以。方法也很簡單，我們只需要翻轉第三部分的數組即可。因為如果分析一下可以發現，我們交換了兩個元素的位置之後，並沒有影響第三部分的降序。
那這樣，我們只需要尋找兩個元素，可以在 O(n) 的時間內找到答案。比之前的算法不知道提升了多少，這個算法的本質其實就是貪心，但是需要我們對題目有非常深入的理解才可以做出來。
這些都想明白了之後，代碼就很簡單了，我們來看下：
到這裡整個問題就結束了，從代碼來看這段代碼量並不大，但是想要完美寫出來，並不容易。尤其是變量之間的關係需要詳細地推導，根據我的經驗，結合上圖來思考會容易理解很多。
今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
