R={A1,A2,A3...An}是要进行全排列的序列。设集合R的全排列记为P（R），A1 P（R）表示在R的所有全排列之前加上A1 后得到的全排列。
当n=1时，P（R）=（R）,此时R中只有一个元素；
当n>1时，P（R）由（A1）P(R1),（A2）P(R2),（A3）P(R3)...（An）P(Rn)组成，其中Ri为R除去Ai的其他元素组成。
n=5时，代码如下：
1 #include <iostream> 2 3 using namespace std; 4 5 void Perm(char list[],int k,int m); 6 void Swap(char &a,char &b); 7 int main() 8 { 9 char list[5]={‘A‘,‘B‘,‘C‘,‘D‘,‘E‘}; 10 Perm(list,0,4); 11 return 0; 12 } 13 void Perm(char list[],int k,int m){ 14 if(k==m){ 15 for(int i=0;i<=m;i++) 16 cout<<list[i]; 17 cout<<endl; 18 } 19 else 20 for(int i=k;i<=m;i++){ 21 Swap(list[k],list[i]); 22 Perm(list,k+1,m); 23 Swap(list[k],list[i]); 24 } 25 } 26 void Swap(char &a,char &b){ 27 int temp=a; 28 a=b; 29 b=temp; 30 }
可以只用三个元素单步跟踪下程序的运行，就明白了逐步递归的过程。
P（ABC）={A P(BC),B P(AC),C P(AB)}
={A B P(C),A C P(B);B A P(C),B C P(A);C A P(B),C B P(A)}
={ABC,ACB;BAC,BCA;CAB,CBA}
代码中
|
1
2
3
4
5
|
for(int
i=k;i<=m;i++){
Swap(list[k],list[i]);
Perm(list,k+1,m);
Swap(list[k],list[i]);
} |
两次交换就是在输出一个递归分支之后将原序列还原，保持原序列不变，类似的处理下一个递归分支。
来源：http://blog.163.com/blue_boy29/blog/static/76212945200971093732817/