算法笔记之 全排列算法 一 递归求解
集合R={1,2,3,4}的全排列
可以分解为：1,{2,3,4}的全排列 + 2,{1,3,4}的全排列 + 3,{1,2,4}的全排列 + 4,{1,2,3}的全排列。
继续分解：{2,3,4} 为 2,{3,4}的全排列，3,{2,4}, 4,{2,3}………………………………
…………
直到集合里只有一个元素，就可直接输出了.
[cpp]
#include <iostream>
using namespace std;
//char * str;
//int len = 2;
/**
*产生list[start:end]的所有排列, 通常为0，len-1
*/
template <class Type>
void Perm(Type list[],int start,int end){
//单元素序列
if( start == end){ //即此时集合里只有一个元素
for(int i=0; i<=end; i++)
cout << list[i];
cout << endl;
}
//多元素序列，递归产生排列
else{
for(int i= start; i<= end; i++){
Swap(list[start], list[i]);//交换可得：1,{2,3,4} ; 2,{1,3,4}; 3,{1,2,4}; 4,{1,2,3}
Perm(list, start+1, end);
Swap(list[start], list[i]);//输出排列之后，要再交换回到初始状态:{1,2,3,4}
}
}
}
template <class Type>
inline void Swap(Type &a, Type &b){
Type temp = a;
a = b;
b = temp;
}
int main() {
char str[] = "abcd";
Perm(str, 0,3);
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}
输出：
abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc
补充：软件开发 , C++ ,
