问题描述：
对于一个给定的序列 a = [a1, a2, a3, … , an]，请设计一个算法，用于输出这个序列的全部排列方式。
例如：a = [1, 2, 3]
输出
123
132
213
231
321
312
基于递归方法：
思路讲解：
（1） 一个元素的序列全排列是其本身
（2）对于一个n个元素的序列（没有重复元素）而言，我们可以把其分解为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);
}
输出结果如下：
123
132
213
231
321
312
Program ended with exit code: 0
如果序列中有重复的元素，那么我们只需保证，在每个子问题中相同的重复元素只能做一次首元素就可以避免重复计算的情况。
代码如下：
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]中的元素有重复的，则不进行后面的交换和全排列
// 否则进行后面的交换和全排列。这样保证每个子问题中，重复元素只有一次作为首元素
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);
}
输出结果：
2000
0200
0020
0002
Program ended with exit code: 0
基于枚举法（循环实现）
我们先假设序列是没有重复元素的。因此全排列的所有可能情况组成的序列大小各不相同。基于此，我们想可以通过大小来枚举所有的序列：
如果第i个排列是[A0, A1, A2, A3, ……]，则第i+1个序列就是比这个序列[A0, A1, A2, A3, ……]大的所有序列中最小的那个。
算法如下（从小到大枚举所有序列）：
准备阶段，为了初始数列是按照从小到大排列的，我们对序列进行排序（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]的元素全部逆序
思路讲解：
第一步，我们从后往前两两比较，找到第一个满足前一个元素小于后一个元素的地方（其实这一步就保证了该地方后面是升序的。因为元素互异，所以是严格升序的。这个对于后面全部反转逆序的理解很关键）。
第二步，从a[i+1]开始往后找，找到一个大于a[i]中最小的一个元素，这个元素的下标记为j，交换a[i]和a[j]。这时，因为原本后面是严格升序的，且找到的元素又是大于a[i]中最小的一个。所以被调换的这个元素a[j]肯定大于其后面的元素，并且后面的那个元素肯定小于或等于a[i]的（不然，a[j]就不是大于a[i]的元素中最小的一个）。因此，此处可以得出调换过后，从a[i+1]开始到末尾还是严格升序的。
第三步，由上面可知，后面元素还是严格升序排列的，所以我们需要将其反转得到全排列所有序列中比上一个序列大且是最小的一个序列。
从上面我们可以知道，其实有重复元素是一样的。因为在第二步中找大于a[i]中最小的一个，如果有重复元素在，总是会找到最后一个并记录下它的index为j。所以交换过后依然保证后面是升序的。则保证了最后一步反转的正确性。
代码如下：
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;
}
// 此函数需要传入排序好的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);
}
结果如下：
012
021
102
120
201
210
Program ended with exit code: 0
