全排列?

（遞歸樹(shù)圖之后會(huì)更新，兩星期之內(nèi)）

今天花時(shí)間來(lái)熟悉的是全排列，據(jù)網(wǎng)上資料透露?？迹容^經(jīng)典，同時(shí)能考察考生的遞歸的功底，進(jìn)一步也能考察考生非遞歸的實(shí)現(xiàn)，所以很能考察考生的基本功。我一開(kāi)始理解程序也有點(diǎn)困難所以畫了個(gè)棧圖，希望大家也都能搞明白，如果理解了給我點(diǎn)個(gè)贊吧，蟹蟹大家！

全排列是什么？

舉個(gè)栗子：

將整型數(shù)組[1,2,3] 進(jìn)行全排列，你將會(huì)得到[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]，總共是六個(gè)結(jié)果，根據(jù)給的整型數(shù)組的值，進(jìn)行不同位置的排序，得到原數(shù)組中所有元素不同排列的結(jié)果。

為什么是六個(gè)結(jié)果？

根據(jù)全排列的計(jì)算公式：f(n)=n!(定義0!=1)

n代表我們的數(shù)組長(zhǎng)度，我們的數(shù)組長(zhǎng)度是3，所以將3帶進(jìn)去，我們能得到3 * 2 * 1 = 6

題目輸入：

整數(shù)類型的array，array中的每個(gè)元素都是唯一的

解題思路：

例如我們有一個(gè)數(shù)組 [ 1, 2, 3 ] 我們需要對(duì)他們進(jìn)行全排列，

我們選 1 作為第一個(gè)數(shù)字，然后我們需要對(duì)其他數(shù)字進(jìn)行全排列，第二個(gè)數(shù)字可以是2 也可以是 3，所以我們獲得了 [ 1, 2 ] 和 [ 1, 3 ]。然后我們?cè)賹?duì)接下來(lái)的數(shù)字進(jìn)行全排列，我們就會(huì)得到結(jié)果 [ 1, 2, 3 ] 和 [ 1, 3, 2 ]。

如果我們 我們選擇 2 作為第一個(gè)數(shù)字，我們將它從原來(lái)的數(shù)組中移除，那原數(shù)組就只剩下[ 1, 3 ]，接下來(lái)我們繼續(xù)進(jìn)行全排列，我們就獲得了 [ 2, 1]，因?yàn)槲覀兊诙€(gè)數(shù)字選擇了 1 所以我們需要在原數(shù)組中移除1，因此原數(shù)組只剩下 [3]，我們?cè)賹?duì)第三個(gè)數(shù)全排列選擇，因此我們得到了[ 2, 1, 3 ]。第二次我們繼續(xù)重復(fù)剛剛操作，我們就能得到 [ 2, 3, 1 ]這個(gè)數(shù)組。

全排列第二個(gè)數(shù)字

簡(jiǎn)單的總結(jié)一下上面的例子，

我們需要選擇第一個(gè)數(shù)字，然后將它從原數(shù)組中移除，然后開(kāi)始全排列第二個(gè)數(shù)字，然后再將它移除，再全排列第三個(gè)數(shù)字，直到原數(shù)組中的數(shù)字都被遍歷完了，我們就得到全排列的答案。

中場(chǎng)回顧：

我們知道如何去選取第一個(gè)數(shù)字，第二個(gè)數(shù)字 ... 直到第n個(gè)數(shù)字，我們還介紹了總共有多少種可能性，因此我們?cè)谶x擇第一個(gè)數(shù)字的時(shí)候，我們有n種可能性，第二個(gè)數(shù)字的時(shí)候我們有n - 1種可能性，第三個(gè)數(shù)字我們有n - 2種可行性 ... 直到最后一個(gè)數(shù)字。

接下來(lái)是代碼講解，

這是代碼的偽代碼，我們會(huì)先寫一個(gè)helper方法幫我們實(shí)現(xiàn)之前的所說(shuō)的事情。

1. 在這個(gè)helper方法里面有三個(gè)參數(shù) ———? arr, perm, perms?

????arr參數(shù)代表 array 意思是我們需要傳入的原來(lái)的數(shù)組，如果我們要求[ 1，2，3 ]的全排列我們就輸入[ 1，2，3 ]

????perm的意思是permutation，存儲(chǔ)的是當(dāng)前正在全排列的數(shù)組，比如我們一開(kāi)始選擇了 1 作為第一個(gè)數(shù)就傳入 [ 1 ]

????perms的意思是permutations，存儲(chǔ)的是全排列完成了的數(shù)組，例如我們得到了全排列的數(shù)組 [ 1，3，2 ]我們就能添加到perms里面

2. 如果arr是空的，就說(shuō)明我們完成了一個(gè)全排列，因?yàn)槲覀兠考尤胍粋€(gè)數(shù)到perm中我們就需要在原來(lái)的數(shù)組中移除相同的數(shù)字

3. 如果arr不是空的說(shuō)明我們前排列哈沒(méi)有完成，我們選擇全排列中的第一個(gè)數(shù)字，然后將它從原數(shù)組中移除，然后將存儲(chǔ)當(dāng)前正在全排列的變量perm中。原數(shù)組[ 1, 2, 3 ]我們選擇了 1 然后加入到perm中， perm就是 [ 1 ]，然后移除之后原數(shù)組就是[ 2, 3 ]。

4. 我們已經(jīng)選擇了第一個(gè)數(shù)，所以我們要對(duì)后面的數(shù)字進(jìn)行全排列了，所以我們傳入新的原數(shù)組，新的perm，和permutations（存儲(chǔ)全排列好的對(duì)象的數(shù)組）到helper方法里面。

小總結(jié)一下：判斷排列好沒(méi)有，沒(méi)有排列好就繼續(xù)選擇原數(shù)組中的元素，選擇一個(gè)之后從原數(shù)組中移除，添加到正在全排列的變量 perm中，然后除了被選擇得數(shù)字后面的數(shù)字也要進(jìn)行全排列，所以再次調(diào)用helper方法！

空間復(fù)雜度講解：

空間復(fù)雜度是O(n * n!)，我們創(chuàng)建了一個(gè)存儲(chǔ)數(shù)組，存儲(chǔ)全排列的結(jié)果，結(jié)果總共是N! 種，同時(shí)每個(gè)可能性長(zhǎng)度是N，所以時(shí)間復(fù)雜度是O(n * n!)

時(shí)間復(fù)雜度講解，

圖1第一個(gè)判斷列表是否為空我們需要執(zhí)行 n！次，因?yàn)槲覀兛偣灿衝！種可能，當(dāng)所有的原列表種的元素移除完了，才能證明我們的全排列做好了所以這里的時(shí)間復(fù)雜度是O(n！)。

我們每次想獲得一種全排列的答案我們都需要遍歷一整個(gè)列表所以這里的時(shí)間復(fù)雜度是O(n)。

我們每次還需要移除n個(gè)元素，因?yàn)橐瞥炅怂械脑斜碇械脑兀拍苷f(shuō)明我們?nèi)帕型瓿闪耍@個(gè)時(shí)間復(fù)雜度是O(n)。

因此最終的時(shí)間復(fù)雜度是O(n! * n * n) 也就是O(n! * n^2)

圖1

這個(gè)是對(duì)圖1進(jìn)行補(bǔ)充說(shuō)明，最下面的葉子節(jié)點(diǎn)代表最終的全排列的結(jié)果，總共有n!個(gè)，我們需要通過(guò)n次的遍歷才能拿到一個(gè)結(jié)果。我們同時(shí)也要移除n個(gè)元素。所以最終的時(shí)間是O(n! * n^2)

圖2 圖1的補(bǔ)充說(shuō)明

代碼

如果看不懂的可以拉下去看程序運(yùn)行的棧圖?。。?！

需要沒(méi)有注釋的可以拉到最下面，

程序運(yùn)行的棧圖（可能用樹(shù)狀圖會(huì)更好理解，稍后會(huì)更新樹(shù)狀圖）

三個(gè)list對(duì)應(yīng)著helper方法的三個(gè)參數(shù)? arr? perm perms? ?（arr 的意思是array， perm的意思是permutation， perms的意思是permutations

程序棧圖

沒(méi)有注釋的版本

未優(yōu)化版本

如果你成功看到這里，讓我們來(lái)講講如何優(yōu)化這個(gè)代碼！

如何讓我們的時(shí)間復(fù)雜度降低一個(gè)n

我們可以不需要移除list中的元素，取而代之的是我們使用指針，說(shuō)明如圖

小總結(jié)一下，我們想要做的事情是！選擇一個(gè)數(shù)字，然后全排列它后面的數(shù)字和，選擇了1 全排列 2 3 選擇了 1 2 全排列后面的 3，再實(shí)際中我們的傳的可能不是一個(gè)長(zhǎng)度為3的數(shù)組，所以我們要一直全排列下去，直到整個(gè)數(shù)組全排列完成。然后我們 undo 也就是取消之前的操作，讓他回到上一層。

偽代碼

偽代碼

偽代碼的解釋說(shuō)明

時(shí)間復(fù)雜度和空間復(fù)雜度：

先說(shuō)空間復(fù)雜度和上面是一樣的也是O(n! * n)，因?yàn)橛衝！個(gè)結(jié)果，每個(gè)結(jié)果的長(zhǎng)度是n

時(shí)間復(fù)雜度是 O(n! * n)，比較占用操作數(shù)的就是 if 判斷下的數(shù)組添加操作，我們需要添加 n長(zhǎng)度的答案，然后我們總共有n！個(gè)結(jié)果，else條件下面的 交換操作都是常數(shù)時(shí)間復(fù)雜度，也就是O(1)，所以我們總共是O(n! * n + 3)兩個(gè)交換操作和一個(gè)方法調(diào)用操作，所以時(shí)間復(fù)雜度更接近O(n! * n)。

代碼：

優(yōu)化后的有注釋的代碼

棧圖

代碼棧圖

優(yōu)化過(guò)的版本

Reference：代碼來(lái)自Algoexpert，以學(xué)習(xí)作為主要目的來(lái)分享的。

如果大家喜歡我的分享可以點(diǎn)一下喜歡謝謝！