关于全排列算法思路的，代码中间一段怎么都看不懂，全排列的具体规律是怎样的？求指教
void allRangle(int arr[], int m, int nLen)全排列?算法?思路
{
if (m == nLen)
{
for (int i = 0; i < nLen; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
else
{
for (int i = m; i < nLen; i++)
{
swap(arr[m], arr[i]);
allRangle(arr, m+1, nLen);
swap(arr[m], arr[i]);
}
}
}
[解决办法]
大概思想就是对每一个位置, 依次选择对应的数来放, 输出每一种放置方法.
首先, 开始的时候 m = 0, 对应位置 0. 通过:
for (int i = m; i < nLen; i++)
{
swap(arr[m], arr[i]);
这个循环, 从 0 到结束的每一个数, 依次尝试把它放到位置 m = 0 上.
然后 m = 1 选择第二个位置的数, 从第二个开始到最后的数依次尝试放到第 2 个位置上.
然后 m = 2 选择地三个位置的数.
...
到 m = nLen - 1, 所有的位置都选好数了.
下一次递归 m = nLen 进行输出.
[解决办法]
求全排列的真正迭代算法比较复杂：
1：将序列D从小到大排序,此为第一个排列。
2：从后向前找到第一个比其后紧邻元素小的元素D[I]
2.1存在I：从后向前找到第一个比元素D[I]大的元素D[J]，这一步必然成功。
2.1.1 交换D[I]与D[J]
2.2.2 将从D[I+1]到表尾的数据逆转,此为下一个排列
2.2不存在I：排序迭代完毕，退出
3：回到第2步。
递归算法要简单一些：
1：判断size==1
1.1 真：全排列只有一个{D[0]}
1.2 假：
1.2.1：I从0到size-1循环：
1.2.1.1：交换D[I],D[0]
1.2.1.2：求D[1]到队尾的全排列，放在D[0]后面
[解决办法]
大致分析了下，不知道能否看到
假如m=5,nLen=10
5-5(交换5，5)
6-6
7-7//i=7,m=7
8-8//i=8,m=8
9-9//i=9,m=9
allRangle(arr, 10, nLen);//m=10=nLen//输出所有 0 1 2 3 4 5 6 7 8 9
9-9//Swap(9,9)
8-8//Swap(8,8)
9-8//i=9,m=8//Swap(8,9)//0 1 2 3 4 5 6 7 9 8
9-9//Swap(9,9)
allRangle(arr, 10, nLen);//m=10=nLen//输出所有 0 1 2 3 4 5 6 7 9 8
9-9//Swap(9,9)
8-9//Swap(8,9)//0 1 2 3 4 5 6 7 8 9
8-7//i=8,m=7//Swap(8,7)//0 1 2 3 4 5 6 8 7 9
8-8//i=8,m=8//Swap(8,8)
9-9//Swap(9,9)
allRangle(arr, 10, nLen);//m=10=nLen//输出所有//0 1 2 3 4 5 6 8 7 9
9-9//Swap(9,9)
8-8//Swap(8,8)
9-8//i=9,m=8//Swap(8,9)//0 1 2 3 4 5 6 8 9 7
9-9
allRangle(arr, m+1, nLen);//m=10=nLen//输出所有 0 1 2 3 4 5 6 8 9 7
9-9
8-9//Swap(8,9)//0 1 2 3 4 5 6 8 7 9
8-7//Swap(8,7)//0 1 2 3 4 5 6 7 8 9
9-7//i=9,m=7//Swap(9,7)//0 1 2 3 4 5 6 9 8 7
8-8//i=8,m=8//Swap(8,8)
9-9//Swap(9,9)
allRangle(arr, 10, nLen);//m=10=nLen//输出所有//00 1 2 3 4 5 6 9 8 7
9-9//Swap(9,9)
8-8//Swap(8,8)
9-8//i=9,m=8//Swap(8,9)//0 1 2 3 4 5 6 9 7 8
9-9
allRangle(arr, m+1, nLen);//m=10=nLen//输出所有 0 1 2 3 4 5 6 9 7 8
9-9
8-9//Swap(8,9)// 0 1 2 3 4 5 6 9 8 7
9-7//Swap(8,7)// 0 1 2 3 4 5 6 7 8 9
......
[解决办法]
//全排列的生成算法
// 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，
// 因此在此就以n个数字的排列为例说明排列的生成法。
// n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从
// 它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
// 全排列的生成法通常有以下几种：
// 字典序法
// 递增进位数制法
// 递减进位数制法
// 邻位交换法
// 递归类算法
//1.字典序法 效率高且顺序自然
// 字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345，排列12345在前，
// 排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是54321。
// 字典序算法如下：
// 设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
// 1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i
[解决办法]
pi<pi+1}
// 2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i
[解决办法]
pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
// 3）对换pi，pk
// 4）再将pj+1......pk-1pkpk+1pn倒转得到排列p’’=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。
// 例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
// 自右至左找出排列中第一个比右边数字小的数字4 839647521
// 在该数字后的数字中找出比4大的数中最小的一个5 839647521
// 将5与4交换 839657421
// 将7421倒转 839651247
// 所以839647521的下一个排列是839651247。
//2.递增进位数制法
// 在递增进位制数法中，从一个排列求另一个排列需要用到中介数。如果用 ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数，则排列的中介数就是对应的
// 排列k1 ...... ki...... kn-1。
// 例如排列839647521的中介数是72642321，7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。
// 中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1，需要注意的是，如果中介数的
// 末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1，则要进位，这就是所谓的递增进位制。例如排列839647521的中介数是72642321，则下一个排列的中介数
// 是67342221+1=67342300（因为1+1=2，所以向前进位，2+1=3，又发生进位，所以下一个中介数是67342300）。
// 得到中介数后，可根据它还原对应得排列。
// 算法如下：
// 中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数，因此，要按k1、k2、......、kn-1的值从右向左
// 确定n、n-1、......、2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字，则该位置不算在内，最后一个空位放1。
// 因此从67342300可得到排列849617523，它就是839647521的后一个排列。因为9最先放置，k1=6，9放在右起第7位，空出6个空位，然后是放8，k2=7，8放在右起第8位，
// 但9占用一位，故8应放在右起第9位，余类推。
//3.递减进位制数法
// 在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。
// 839647521的中介数是67342221(k1k2...kn-1)，倒转成为12224376(kn-1...k2k1)，这是递减进位制数的中介数：ki(i=n-1,n-2,...,2)位逢i向ki-1位进1。给定排列p，
// p的下一个排列的中介数定义为p的中介数加1。例如p=839647521，p的中介数为12224376，p的下一个排列的中介数为12224376+1=12224377，由此得到p的下一个
// 排列为893647521。
// 给定中介数，可用与递增进位制数法类似的方法还原出排列。但在递减进位制数中，可以不先计算中介数就直接从一个排列求出下一个排列。具体算法如下：
// 1）如果p(i)=n且i<>n，则p(i)与p(i-1)交换
// 2）如果p(n)=n，则找出一个连续递减序列9、8、......、i，将其从排列左端删除，再以相反顺序加在排列右端，然后将i-1与左边的数字交换
// 例如p=893647521的下一个排列是983647521。求983647521的下一个排列时，因为9在最左边且第2位为8，第3位不是7，所以将8和9从小到大排于最右端364752189，
// 再将7与其左方数字对调得到983647521的下一个排列是367452189。又例如求987635421的下一个排列，只需要将9876从小到大排到最右端并将5与其左方数字3对调，
// 得到534216789。
//4.邻位对换法 效率最高但顺序不自然
// 邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。以4个元素的排列为例，将最后的元素4逐次与前面的元素交换，可以生成4个新排列：
// 1 2 3 4, 1 2 4 3, 1 4 2 3, 4 1 2 3
// 然后将最后一个排列的末尾的两个元素交换，再逐次将排头的4与其后的元素交换，又生成四个新排列：
// 4 1 3 2, 1 4 3 2, 1 3 4 2, 1 3 2 4
// 再将最后一个排列的开头的两个元素交换，将4从后往前移：
// 3 1 2 4, 3 1 4 2, 3 4 1 2, 4 3 1 2
// 如此循环4!次既可求出全部排列。
//5.元素增值法（n进制法）效率低
// 1）从原始排列p=p1p2......pn开始，第n位加n-1，如果该位的值超过n，则将它除以n，用余数取代该位，并进位（将第n-1位加1）
// 2）再按同样方法处理n-1位，n-2位，......，直至不再发生进位为止，处理完一个排列就产生了一个新的排列
// 3）将其中有相同元素的排列去掉
// 4）当第一个元素的值>n则结束
// 以3个数1、2、3的排列为例：原始排列是1 2 3，从它开始，第3个元素是3，3+2=5，5 Mod 3=2，第2个元素是2，2+1=3，所以新排列是1 3 2。通过元素增值，顺序产生的
// 排列是：1 2 3，1 3 2，2 1 1，2 1 3，2 2 2，2 3 1，2 3 3，3 1 2，3 2 1
// 有下划线的排列中存在重复元素，丢弃，余下的就是全部排列。
//6.递归类算法
// 全排列的生成方法用递归方式描述比较简洁，实现的方法也有多种。
// 1）回溯法
// 回溯法通常是构造一颗生成树。以3个元素为例；树的节点有个数据，可取值是1、2、3。如果某个为0，则表示尚未取值。
// 初始状态是(0，0，0)，第1个元素值可以分别挑选1，2，3，因此扩展出3个子结点。用相同方法找出这些结点的第2个元素的可能值，如此反复进行，一旦出现新结点的3个
// 数据全非零，那就找到了一种全排列方案。当尝试了所有可能方案，即获得了问题的解答。
// 2）递归算法
// 如果用P表示n个元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前缀i的排列，那么，n个元素的排列可递归定义为：
// 如果n=1，则排列P只有一个元素i
// 如果n>1，则排列P由排列(i)Pi构成（i=1、2、....、n-1）。
// 根据定义，容易看出如果已经生成了k-1个元素的排列，那么，k个元素的排列可以在每个k-1个元素的排列Pi前添加元素i而生成。例如2个元素的排列是1 2和2 1，对与个
// 元素而言，p1是2 3和3 2，在每个排列前加上1即生成1 2 3和1 3 2两个新排列，p2和p3则是1 3、3 1和1 2、2 1，按同样方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。
// 3）循环移位法
// 如果已经生成了k-1个元素的排列，则在每个排列后添加元素k使之成为k个元素的排列，然后将每个排列循环左移（右移），每移动一次就产生一个新的排列。
// 例如2个元素的排列是1 2和2 1。在1 2 后加上3成为新排列1 2 3，将它循环左移可再生成新排列2 3 1、3 1 2，同样2 1 可生成新排列2 1 3、1 3 2和3 2 1。
[解决办法]
你首先搞清楚这个函数是什么意思.弄清楚每个参数的意思。从代码来看，这个程序并不是单纯的对整个数组进行全排列，从第2个参数m的使用来看，这个程序是对数组的某个指定的区间进行排列。
比如数组 int arr[4] = {1,3,5,7}; allRange(arr, 2, 4);这个调用只是对数组的区间[2,4)进行排列，
注意这个区间是半开半闭的区间。 [2,4)区间内的元素是{5,7}，很显然这段区间的排列方式就两种:
1). 5, 7
2). 7, 5
因为[0,2)的区间不进行排列，所以程序的输出就是
1） 1，3，5，7
2） 1，3，7，5
从上述分析，我们知道如果要整个数组进行全排列，那么我们的调用就应该是allRange(arr, 0, 4)，对整个数组区间[0,4)进行排序。
接下来分析这个递归程序。
首先要明确：递归程序具有一个出口和一个出口条件(只有满足该条件才能执行出口语句)。（如果对这个概念不清楚，那就无从谈起了，建议你去看下相关的书籍，了解递归的概念）。
一般来说：出口语句都是return形式的语句。但是由于上面这个函数是个void类型的，而且函数中也没有显示的return，可能导致理解起来有点困难，为了让程序更容易理解，我显示添加return语句，修改后的程序如下：
void allRange(int arr[], int m, int nLen)
{
if (m == nLen) // 出口条件
{
for (int i = 0; i < nLen; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
return; //递归程序的出口;
}
else
{
for (int i = m; i < nLen; i++)
{
swap(arr[m], arr[i]); // 第一个swap语句
allRange(arr, m+1, nLen);
swap(arr[m], arr[i]); // 第二个swap语句
}
}
}
接下来就是分析，程序如何递归最终到达出口。从代码来看，出口的条件的是if(m==nLen)；从代码来看nLen没有改变过，每次递归调用改变的是m值，调用递归函数的时候m值加1（注意:从递归返回时m值减1）显然经过若干次递归调用后一定会满足(m==nLen).最终程序找到出口，return返回。 这里要理解，这个程序达到出口返回就表示完成了一次排列。程序能够多少次达到出口就表示有多少种排列方式。
再来看看递归的过程，以便有个更加感性的认识：
拿之前的那个数组的全排列举例，也就是:int arr[4] = {1,3,5,7}; allRange(arr, 0, 4);
因为for 循环中有两个swap语句，我在下面阐述时:分别用第一个和第二个来区别。
其实第一次swap是交换两个值，接下来再swap一次，其实就还原恢复之前交换的两个值。
首先 allRange(arr, 0, 4) ---> m=0; nLen=4;
接着 i=m ---> i=0 ---> swap(arr[m], arr[i])--->swap(arr[0], arr[0])
arr[0] = 1;
调用allRange(arr, 1, 4);---> m=1;
接着 i=m --->i=1 --->调用第一个swap(arr[m], arr[i])-->swap(arr[1], arr[1])
arr[1] = 3;
调用allRange(arr, 2, 4); ---> m=2;
接着 i=m --->i=2 --->调用第一个swap(arr[m], arr[i])-->swap(arr[2], arr[2]);
arr[2] = 5;
调用allRange(arr, 3, 4); ----> m=3;
接着 i=m --->i=3 --->调用第一个swap(arr[m], arr[i])-->swap(arr[3], arr[3]);
arr[3] = arr[3] = 7;
调用allRange(arr, 4, 4); ----> m=4;
这时 m==nLen==4, 满足出口条件，执行出口语句，找到一个排序: arr[0],arr[1],arr[2],arr[3]
即：1、3、 5、 7。
接下来，执行出口语句，return返回:
首先从allRange(arr, 4, 4) 这个调用返回，
返回到allRange(arr, 3, 4)--->m=3; i=3;
执行第2个swap语句；
swap(arr[m], arr[i])-->swap(arr[3], arr[3]); ---->arr[3] = 7;
接着执行 for 循环的 i++; --> i=4;
因为此时不满足 i<nLen 所以跳出for循环。从allRange(arr, 3, 4)返回；
返回到allRange(arr, 2, 4)--->m=2; i=2;
执行第2个swap语句：
swap(arr[m], arr[i])-->swap(arr[2], arr[2]); ---->arr[2] = 5;
接着执行 for 循环的 i++; --> i=3;
满足 i<nLen; 继续往下执行，执行第一个swap语句；
m=2; i=3;-->swap(arr[m], arr[i]) --->swap(arr[2], arr[3]) --> arr[2]=7, arr[3]=5;
接着调用allRange（arr, 3, 4); --->m=3
接着 i=m --->i=3 --->swap(arr[m], arr[i])-->swap(arr[3], arr[3]);
arr[3] = 5;
接着调用allRange（arr, 4, 4); m=4;
这样又达到出口条件 m==nLen;这样又找到一个排列：arr[0],arr[1],arr[2],arr[3]
即：1、3、7、5.
参考上面的描述，可以继续完成后续的递归分析。
[解决办法]
算法这种东西不是一蹴而就的，而是一个迭代的过程。比如对于全排列这个递归算法，我们可能第一次不能直接写出楼主所贴出来的那种精炼的递归代码。但是我们可以根据自己的理解，写出一个性能稍微差点的递归形式的代码，然后再分析重构代码，最终得到精炼的递归代码。这是我个人理解的算法学习方式，这也是楼主为什么看到那段精炼的代码会觉得吃力的原因，因为你看到的是一个最终的精炼的代码，而没看到这个代码是如何演化得到的。 我们不可能直接跳过原始的分析过程和后续的优化重构过程，一下就得出最精炼的算法代码。
拿全排列来说，如果给定数组集合有4个元素，很自然而然的排列过程是先从集合中选一个元素，然后再选第2个，再选第3个，最后确定第4个，这样就完成一次排列。
按照这个思想，我们很容易就能写一个递归程序。一开始不要追求性能，不要追求技巧，追求的是尽可能的让程序具有类似自然语言的可读性，可理解性，我个人倾向于用C++高级语言来描述算法，个人觉得比C要容易理解，当然性能是不如C的。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<int n>
class Arrangement
{
intm_nData[n]; //要进行排列的数组
intm_nSelectCount; //选择多少个元素了
vector<int> m_vSelectData; //选择了哪些元素
intm_nTotalArrangementNumber; // 总共有多少种排列方式
public:
Arrangement(int (&arr)[n])
{
m_nSelectCount =0;
m_nTotalArrangementNumber = 0;
std::copy(arr, arr+n, m_nData);
}
void RunRecursion()
{
for (int i=0; i<n; ++i)
{
if (m_nSelectCount==n) // 出口条件(已经选择了n个元素，可以完成了一次排列了)
{
++m_nTotalArrangementNumber;
copy(m_vSelectData.begin(), m_vSelectData.end(), ostream_iterator<int>(cout," "));
cout<<endl;
return; // 递归出口
}
if (HasSelected(m_nData[i])) // 避免一个元素在一次排列中被选择多次
{
continue;
}
select(i); // 选中一个元素。
RunRecursion();
remove(i); // 移除前面select()选中的元素。
}
}
int GetArrangementNumber()
{
return m_nTotalArrangementNumber;
}
protected:
bool HasSelected(int m)
{
vector<int>::iterator it = find(m_vSelectData.begin(), m_vSelectData.end(), m);
if(it!= m_vSelectData.end())
return true;
else
return false;
}
void select(int i)
{
m_vSelectData.push_back(m_nData[i]);
++m_nSelectCount;
}
void remove(int i)
{
m_vSelectData.pop_back();
--m_nSelectCount;
}
};
void main()
{
const int cSzie = 4;
int arr[cSzie] = {1, 3, 5, 7};
Arrangement<cSzie> argmt(arr);
argmt.RunRecursion();
cout<<"排列数为："<<argmt.GetArrangementNumber()<<endl;
system("pause");
}
上面这个递归程序，无论从代码精炼程度和代码性能来讲，都不太如意。但是这个程序个人认为是一个非常好的出发点，因为递归的过程相对楼主给出的那个简练的程序来说更容易理解（至少我个人是这么觉得的，不是吗）。
接下来的事，就是后续的分析和代码重构的过程了，经历无数次简练优化重构，最终我们得到了精练的代码形式。
很显然，如果第一次就将最终简练的递归代码呈现在你眼前，对于没有经验的人来说，当然是看不懂，理不清。
所以理解算法的最好方式，个人觉得首先是按照自己的理解，写出最容易理解最自然的代码（不需要考虑性能，不需求考虑技巧）。性能和技巧都是后期优化重构的过程，这自然离不开自身的阅历经验了，可能你没那么幸运能够得到最简练并且性能最优的代码。但是我相信如果你经历了上述这些过程，分析和理解别人给出的优秀简练的代码应该是没什么问题的。 毕竟我们大多数人不需要自己去发明创造新的算法，能够读懂别人的算法就已经能完成很多工作了。