全排列問題（第0屆第1題），排列第0屆1題

全排列問題（第0屆第1題），排列第0屆1題

題目要求

       問題描述：輸入一個可能重復的英文字符串（以逗號作為結束標記），按字典順序無重復輸出其所有可能的排列方式。

       樣例輸入1：abc,

       樣例輸出1：abc  acb  bac  bca  cab  cba

       樣例輸入2：cab,

       樣例輸出2：abc  acb  bac  bca  cab  cba

       樣例輸入3：abb,

       樣例輸出3：abb  bab  bba

 解決方案

       這個問題屬於全排列問題，而且需要解決兩個問題：第一是按字典順序輸出，第二是無重復輸出。為了保證字典順序輸出，需要對輸入的字串先進行一次排序，以便於之後的操作。為了保證無重復輸出，需要在輸出時判斷當前情形是否輸出過，這一點在保證字典順序的情況下很好判斷。

       另外，全排列的一個重要思想是遞歸。要想計算abc的全排列，只需先讓a為首，然後計算bc的全排列，再與a一起輸出，然後讓b為首，計算ac的全排列，最後讓c為首，計算ab的全排列。每個字母為首完畢，都要恢復到對應的初始狀態，以abc為例，它的調用狀態如下：

源碼示例

結果展示

小結

       全排列，關鍵是先遞歸排列後面的，然後再排列前面的。注意for循環與遞歸的聯合使用。