問題描述：
對于一個給定的序列 a = [a1, a2, a3, … , an]，請設(shè)計一個算法，用于輸出這個序列的全部排列方式。
例如：a = [1, 2, 3]
輸出
123
132
213
231
321
312
基于遞歸方法：
思路講解：
（1） 一個元素的序列全排列是其本身
（2）對于一個n個元素的序列（沒有重復(fù)元素）而言，我們可以把其分解為n個子問題：即依次讓每個元素作為首元素，剩下的n-1個元素進行全排列。所以這是個遞歸問題。我們以三個元素的序列舉個例子：
[A0, A1, A2]的全排列等于下面三個全排列的子問題：
A0開頭，拼接上[A1,A2]序列的全排列
A1開頭，拼接上[A0,A2]序列的全排列
A2開頭，拼接上[A0,A1]序列的全排列
然后依次類推，[A1,A2]的全排列等于A1開頭，拼接上[A2]序列的全排列和A2開頭，拼接上[A1]序列的全排列……
代碼如下：
template <class T>
inline void Swap(T& a, T& b)
{
T temp = a; a = b; b = temp;
}
template <class T>
void Permutation(T list[], int start, int end)
{
// 只剩下一個元素，那么就是這個元素本身，并且該列表排序完成可以輸出
if (start == end)
{
for (int i = 0; i < end; i++)
{
cout << list[i];
}
cout << endl;
}
// 否則，我們遍歷所有從start到end的元素作為第一個元素，剩余元素進行全排列
else
{
for (int i = start; i < end; i++)
{
Swap(list[start], list[i]);
Permutation(list, start + 1, end);
Swap(list[start], list[i]);
}
}
}
int main()
{
int my_list[3] = {1, 2, 3};
Permutation(my_list, 0, 3);
}
輸出結(jié)果如下：
123
132
213
231
321
312
Program ended with exit code: 0
如果序列中有重復(fù)的元素，那么我們只需保證，在每個子問題中相同的重復(fù)元素只能做一次首元素就可以避免重復(fù)計算的情況。
代碼如下：
template <class T>
inline void Swap(T& a, T& b)
{
T temp = a; a = b; b = temp;
}
template <class T>
bool whetherSwap(T list[], int start, int end)
{
for (int i = start + 1; i < end; i++)
{
if (list[i] == list[start]) return false;
}
return true;
}
template <class T>
void Permutation(T list[], int start, int end)
{
// 只剩下一個元素，那么就是這個元素本身，并且該列表排序完成可以輸出
if (start == end)
{
for (int i = 0; i < end; i++)
{
cout << list[i];
}
cout << endl;
}
// 否則，我們遍歷所有從start到end的元素作為第一個元素，剩余元素進行全排列
else
{
for (int i = start; i < end; i++)
{
// 如果list[i:end]子問題中，首元素list[i]和剩下部分list[i+1:end]中的元素有重復(fù)的，則不進行后面的交換和全排列
// 否則進行后面的交換和全排列。這樣保證每個子問題中，重復(fù)元素只有一次作為首元素
if (whetherSwap(list, i, end))
{
Swap(list[start], list[i]);
Permutation(list, start + 1, end);
Swap(list[start], list[i]);
}
}
}
}
int main()
{
int my_list[4] = {0, 0, 2, 0};
Permutation(my_list, 0, 4);
}
輸出結(jié)果：
2000
0200
0020
0002
Program ended with exit code: 0
基于枚舉法（循環(huán)實現(xiàn)）
我們先假設(shè)序列是沒有重復(fù)元素的。因此全排列的所有可能情況組成的序列大小各不相同?；诖?，我們想可以通過大小來枚舉所有的序列：
如果第i個排列是[A0, A1, A2, A3, ……]，則第i+1個序列就是比這個序列[A0, A1, A2, A3, ……]大的所有序列中最小的那個。
算法如下（從小到大枚舉所有序列）：
準備階段，為了初始數(shù)列是按照從小到大排列的，我們對序列進行排序（nLog(n)
（1）從后往前兩兩比較，找到第一個滿足a[i]<a[i+1]的兩個元素
（2）從a[i+1]開始往后找，找到一個大于a[i]中最小的一個元素，這個元素的下標記為j，交換a[i]和a[j]
（3）將a[i+1, a.length-1]的元素全部逆序
思路講解：
第一步，我們從后往前兩兩比較，找到第一個滿足前一個元素小于后一個元素的地方（其實這一步就保證了該地方后面是升序的。因為元素互異，所以是嚴格升序的。這個對于后面全部反轉(zhuǎn)逆序的理解很關(guān)鍵）。
第二步，從a[i+1]開始往后找，找到一個大于a[i]中最小的一個元素，這個元素的下標記為j，交換a[i]和a[j]。這時，因為原本后面是嚴格升序的，且找到的元素又是大于a[i]中最小的一個。所以被調(diào)換的這個元素a[j]肯定大于其后面的元素，并且后面的那個元素肯定小于或等于a[i]的（不然，a[j]就不是大于a[i]的元素中最小的一個）。因此，此處可以得出調(diào)換過后，從a[i+1]開始到末尾還是嚴格升序的。
第三步，由上面可知，后面元素還是嚴格升序排列的，所以我們需要將其反轉(zhuǎn)得到全排列所有序列中比上一個序列大且是最小的一個序列。
從上面我們可以知道，其實有重復(fù)元素是一樣的。因為在第二步中找大于a[i]中最小的一個，如果有重復(fù)元素在，總是會找到最后一個并記錄下它的index為j。所以交換過后依然保證后面是升序的。則保證了最后一步反轉(zhuǎn)的正確性。
代碼如下：
template <class T>
inline void Swap(T list[], int a, int b)
{
T temp = list[a]; list[a] = list[b]; list[b] = temp;
}
template <class T>
void arrayReverse(T list[], int start, int end)
{
int i = start;
int j = end;
while(j > i){
Swap(list, i, j);
i++;
j--;
}
}
template <class T>
bool Next(T list[], int len)
{
bool exist_next = true;
for (int i = len - 1; i > 0; i--)
{
// 從后往前兩兩比較，找到第一對前面元素大于后面元素的地方
if (list[i - 1] < list[i])
{
int index_swap = i;
for (int j = i + 1; j < len; j++)
{
if (list[j] > list[i - 1])
{
index_swap = j;
}
else if (list[j] < list[i - 1])
{
index_swap = j - 1;
break;
}
}
Swap(list, i-1, index_swap);
arrayReverse(list, i, len - 1);
return exist_next;
}
}
exist_next = false;
return exist_next;
}
// 此函數(shù)需要傳入排序好的list（從小到大）
template <class T>
void Permutation(T list[], int len)
{
for (int i = 0; i < len; i++)
{
cout << list[i];
}
cout << endl;
while(Next(list, len))
{
for (int i = 0; i < len; i++)
{
cout << list[i];
}
cout << endl;
}
}
int main()
{
int my_list[3] = {0, 1, 2};
Permutation(my_list, 3);
}
結(jié)果如下：
012
021
102
120
201
210
Program ended with exit code: 0
