初步了解全排列的遞歸實作

首先先推薦一個講解全排列的視訊：[算法教程] 全排列

我個人認為對于新手來說比較好了解，雖然我也看了好多的部落格，但發現說的都是一句話：要想了解遞歸，先得了解遞歸。 是以一直不太了解，直到看了這個UP主的視訊。強烈推薦哦！

先上全排列遞歸實作的代碼：

public class permAll {
	//交換函數
	public static void swap(char[] str, int a, int b) {
		char temp;
		temp = str[a];
		str[a] = str[b];
		str[b] = temp;
	}
	//全排列的主體函數
	public static void Perm(char[] str, int start, int end) {
		if(start == end) {//如果層數和字元串的長度一緻，說明字元串已經排列完成，可以輸出
			for(int i=0; i<=end; i++) {
				System.out.print(str[i]);
			}
			System.out.println();
		}else {
			for(int i=start; i<=end; i++) {
				swap(str,i,start);//讓第一個元素依次和後面的元素交換位置
				Perm(str,start+1,end);
				swap(str,i,start);//将字元串的順序歸位，友善下一次位置的交換
			}
		}
	}
	public static void main(String[] args) {
		char[] str = {'a','b','c'};
		Perm(str,0,str.length-1);
	}
}
           

首先說明一下全排列主體函數的三個參數：

Perm(char[] str, int start, int end);

Perm(str, 0, str.length-1);

第一行語句中的

str

指的是需要進行全排列的字元串（這裡用字元數組表示）；

start

指的是全排列開始的位置，

end

指的是全排列結束的位置，也就是說我需要對字元串中從

start

開始到

end

結束的連續子字元串進行全排列。

那麼第二行語句就是指對str這個字元串本身進行全排列。

下面是最關鍵的地方

for(int i=start; i<=end; i++) {
	swap(str,i,start);
	Perm(str,start+1,end);
	swap(str,i,start);
}
           

先說這個

for循環

：

首先我們達成一緻的是，

[1, 2, 3, 4]

的全排列分為：

1開頭

如1，2，3，4

2開頭

如2，1，3，4

3開頭

如3，2，1，4

4開頭

如4，2，3，1

也就是說我們需要分别處理

1開頭，2開頭，3開頭，4開頭

的情況，對每一種情況分别進行全排列。每完成一種就是一次循環。

那麼在這次循環裡面，假設這是第一次循環，也就是處理

1開頭

的情況，那麼我就要把1挪到首位，這裡呢就是1和1交換，其實就是沒動，挪完之後我們就要對這種情況進行全排列的處理。這裡用到遞歸。我們剛開始說過，

Perm(str, 0, str.length-1);

是對完整的字元串進行全排列。現在我已經固定了第一位是1，那麼我們需要處理的是從第二位開始到末尾的字元串的全排列。想要處理從第二位開始到末尾的字元串的全排列，我們是不是需要處理從第三位開始到末尾的字元串的全排列。。。。直到最後隻剩下一個字元，它的全排列就隻有它自己。這時候就可以終止遞歸了。

這個過程确實是很複雜，是以可以不用看。其實遞歸的本質是将某一個問題一步步分成小份，然後進行處理。我舉個例子。假如我想要吃一根面條，但是我舍不得一口吃掉，是以我先把它切分成一段一段，想象一下我們把這根面條固定在桌子上，然後用刀子從左切到右。哎呀終于切完了，我已經餓的不行了，我趕緊從最右邊拿起一小段開始吃，從右吃到左。

我們可以把切面條的過程認為是列舉所有問題的過程，把開始吃認為是解決問題的過程。這整個切分和吃掉的過程就是遞歸。也就是說一次遞歸會解決掉一類問題。

是以

Perm(str,start+1,end);

是指使用遞歸處理start+1到end之間的字元序列。如果start是從0開始，那麼上面這個語句處理的就是下标從1開始到字元串的末尾之間子字元串。也就是

[1, 2, 3, 4]

中的

[2, 3, 4]

，然後再次調用自身，處理

[3, 4]

，直到最後隻剩下一個字元無法處理了，這就是遞歸邊界。等到這個遞歸調用結束的時候，我們其實已經處理完了

1開頭

的所有情況。

我們本應該直接進入下一次循環，處理

2開頭

的情況。但是我們是不是應該先把這個字元串恢複到初始的狀态

[1, 2, 3, 4]

呀，這樣可以避免之後的處理出現重複。我們舉個例子。假設我們要處理的字元串是

[1, 2, 3]

，我們處理完

1開頭

的情況的時候，字元串的位置是

[1, 3, 2]

；如果我們直接進行下一次循環并且進行了交換，那麼情況是這樣子的

[3, 1, 2]

（我們進行交換的前提是按照字元在字元串中的先後順序依次和第一位進行交換）。這種情況有一種排列是這樣子的

[3, 2, 1]

。那麼進行第三次循環并且交換的時候是不是又變成了

[1, 2, 3]

？也就是說出現了重複。

是以說把字元串進行複位操作是必要的。也就是循環體中的第三句。

這就是大概的一個過程，新手很不容易了解。可能我現在的了解也不是很充分很正确，但是也許若幹時間之後再回來看的時候會有更深的了解。

還有一點要說的是，關于代碼中參數命名的問題，很多部落格中寫的是start對應的是k，end對應的是m，說實話我從頭到尾一直沒了解這兩個參數什麼意思。

話說回來，還是推薦去看看我在文章開始貼的視訊連結，up主講的很不錯，而且看視訊可能比看部落格要了解的更深一些。

接下來更新一下如果給的字元串中有重複的字元該如何處理。 我使用的方法是借助`ArrayList`， 每當生成一個排列，借助Arrays的toString方法将字元數組轉換為字元串。然後添加到ArrayList中，在此之前，我們需要判斷一下，如果ArrayList中已經包含了該排列，則不添加，否則添加。代碼如下：

if(start == end) {//如果層數和字元串的長度一緻，說明字元串已經排列完成，可以輸出
	String newStr = Arrays.toString(str);
		if(!arrList.contains(newStr)) {
			arrList.add(newStr);				
		}
	}
           

例如給[1, 2, 2]進行全排列，使用上述方法後産生的結果是：

[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
           

這種方法是一種偷懶的方式，它的時間效率不高，之後我還會繼續學習更樸素的實作方式！