算法笔记之 全排列算法 一 递归求解
集合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}………………………………
…………
直到集合里只有一个元素，就可直接输出了.
#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