要研究一下算法，水平很差，只好各种向大神们学习了。。。然后写个总结，感谢各路大神！
一、全排列的递归算法
先上代码，乃懂的
<span style="font-size:14px;">#include<iostream>
using namespace std;
template <class T>
void Swap(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
template<class T>
void Perm(T list[], int begin, int end)
{
if(begin == end)
{
for(int i = 0; i <= end; ++i)
{
cout << list[i] << " ";
}
cout << endl;
}
else
{
for (int i = begin; i <= end; ++i)
{
Swap(list[begin], list[i]);
Perm(list, begin+1, end);
Swap(list[begin], list[i]);
}
}
}
int main()
{
int list[5] = {1,2,3,4,5};
Perm(list, 0, 4);
return 0;
}</span>
结果就不上图了...
分析如下：
1.假如我们只有两个数字：12.要对它进行全排列，第一种方式就是12本身，第二种，将12交换，变为21即可。这提示了我们一种交换的思路。
2.假如我们要对123进行全排列。我们可以采用将1固定，“23”进行全排列，将“2”固定，对“13”进行全排列。将“3”固定，对“12”进行全排列。
这其实就是首部为”1“，然后是“2”，然后是“3”，不就是第二位后边的数依次和第一位进行交换么？这是典型的递归的思路。
3.我们每次交换要将排列恢复成为原始的“123”，因为这个算法求排列的时候，前后并没有依赖性，其参考物只有“123”这个原始的第一个排列。否则，如果我们不恢复的话，就会出现，虽然数量与正确解法相同，但是会有重复的排列的现象。
二、全排列的非递归算法
继续先代码：
#include <iostream>
using namespace std;
template<class T>
void Swap(T &a, T &b)
{
T temp;
temp = a;
a = b;
b = temp;
}
template<class T>
void Print(T *Array, int length)
{
for (int i = 0; i < length; i++)
{
cout<<Array[i];
}
cout << endl;
}
template<class T>
bool NextSequence(T *Array, int length)
{
int flag = 0;//标志位
int i, j;
int current;
for (i = length-1; i > 0 ; i--)//从后往前找，直到找到某一个值，比其后相邻的值小。
{
if (Array[i-1] < Array[i])
{
flag = 1;//存在
current = i-1;//记录位置
break;
}
}
if (flag == 1)
{
int temp = current+1;
for (int i = current+1; i < length; i++)//在当前位置值的后面找恰好比这个值大的值
{
if (Array[i] < Array[temp] && Array[i] > Array[current])
{
temp = i;
}
}
Swap(Array[temp], Array[current]);//然后交换
//反向操作
for (i = current+1, j = length-1; i < j; i++, j--)
{
Swap(Array[i], Array[j]);
}
return true;
}
return false;
}
int main()
{
int Array[5] = {1,2,3,4,5};
Print(Array, 5);
while (NextSequence(Array, 5) == true)
{
Print(Array, 5);
}
return 0;
}
算法大体思路：
比如说有1234四个数字，要将这四个数字实现全排列。“1234”当然是第额一个排列，第二个排列，选取刚好比它大的，我们用大脑当然想的到是“1243”，然后思路如下：
1.从后往前寻找，即沿着4->3->2->1的方向寻找，直到找到某一个数，它比后面的那个数字小。在“1234”中，我们找到了3，因为3比4小，然后将3和4交换就得到比刚好比"1234"大的一个新全排列为"1243".
2.但是这样有bug。。。比如：在某一个时间，我们产生了一个新的排列：“2143”。依据刚才的思路，我们很容易找了1比4小，然后我们将1和4交换了，得到“2413”.这真的是刚好比“2143”大的全排列么？不是，而是“2314”。所以不是让1和紧挨着他的4交换，而是让1和其后最小的比1大的数交换，“4”和“3”，刚好比“1”大的数字应该是3，所以，我们让“1”和“3”交换，得到“2341”。
3.接着，发现还是有bug，应该是“2314”啊。。因为交换后，“3”这个位置以后的数，当然都是从大到小排列的。。只要做一次反向操作就好了。。即将“41”反向，变为“14”。。好了，就得到“2314”了。。
这解释，给力啊！