字符串的全排列问题：
给定字符串S[0...N-1]，设计算法，枚举字符串的全排列。
1、无重复字符串全排列非递归算法
程序实现：
1 //无重复字符串的全排列递归算法 2 void Permutaion(int* a,int size,int index){ 3 if(index == size-1){ 4 Print(a,size); 5 return; 6 } 7 for(int i=index;i<size;i++){ 8 swap(a[i],a[index]); 9 Permutaion(a,size,index+1); 10 swap(a[i],a[index]); 11 } 12 }
运行结果：
说明：在每次递归前需要保证字符串的顺序不变，因此有每次的替换过程。
2、有重复字符串队规算法
程序实现：
1 //判断从a[to]是否与(index,to)重复 2 bool IsDuplicate(int* a,int index,int to){ 3 while(index<to){ 4 if(a[index]==a[to]){ 5 return true; 6 } 7 index++; 8 } 9 return false; 10 } 11 //有重复字符串的全排列递归算法，Time Cost O((n+1)!) 12 void Permutaion1(int* a,int size,int index){ 13 if(index == size-1){ 14 Print(a,size); 15 return; 16 } 17 for(int i=index;i<size;i++){ 18 if(!IsDuplicate(a,index,i)){ 19 swap(a[i],a[index]); 20 Permutaion1(a,size,index+1); 21 swap(a[i],a[index]); 22 } 23 } 24 }
运行结果：
说明：本算法时间复杂度能达到O((n+1)!)，不可取。
改进：利用空间换时间，采用下列的程序实现：
1 //有重复字符串的全排列递归算法，空间换时间 2 void Permutaion2(int* a,int size,int index){ 3 if(index == size-1){ 4 Print(a,size); 5 return; 6 } 7 int dup[256] = {0}; 8 for(int i=index;i<size;i++){ 9 if(dup[a[i]]==1) 10 continue; 11 dup[a[i]] = 1; 12 swap(a[i],a[index]); 13 Permutaion2(a,size,index+1); 14 swap(a[i],a[index]); 15 } 16 }
运行结果：
3、使用求下一个排列的思想，构造非递归算法。
过程：从当前排列生成字典序刚好比它大的下一个排列。
程序实现：
1 //字符串全排列非递归算法，求下一个排列的思想 2 void Reverse(int* from,int* to){ 3 int t; 4 while(from<to){ 5 t = *from; 6 *from = *to; 7 *to = t; 8 from++; 9 to --; 10 } 11 } 12 bool GetNextPermutation(int* a,int size){ 13 //后找，从后向前找最后一个升序的位置 14 int i = size-2; 15 while((i>=0)&&(a[i]>=a[i+1])) 16 i--; 17 if(i<0) return false; 18 //查找，从后面的元素中寻找比a[i]大的最小值a[j] 19 int j=size-1; 20 while(a[j]<=a[i]) 21 j--; 22 //交换 23 swap(a[i],a[j]); 24 //翻转 a[i+1...N-1] 25 Reverse(a+i+1,a+size-1); 26 return true; 27 }
运行结果：
说明：非递归算法天然解决重复字符问题。
另附上全部实现程序，仅供参考：
1 /*************************************** 2 FileName StringPermutation.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/1 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 void Print(const int* a,int size){ 16 for(int i=0;i<size;i++){ 17 cout<<a[i]<<' '; 18 } 19 cout<<endl; 20 } 21 //无重复字符串的全排列递归算法 22 void Permutaion(int* a,int size,int index){ 23 if(index == size-1){ 24 Print(a,size); 25 return; 26 } 27 for(int i=index;i<size;i++){ 28 swap(a[i],a[index]); 29 Permutaion(a,size,index+1); 30 swap(a[i],a[index]); 31 } 32 } 33 //判断从a[to]是否与(index,to)重复 34 bool IsDuplicate(int* a,int index,int to){ 35 while(index<to){ 36 if(a[index]==a[to]){ 37 return true; 38 } 39 index++; 40 } 41 return false; 42 } 43 //有重复字符串的全排列递归算法，Time Cost O((n+1)!) 44 void Permutaion1(int* a,int size,int index){ 45 if(index == size-1){ 46 Print(a,size); 47 return; 48 } 49 for(int i=index;i<size;i++){ 50 if(!IsDuplicate(a,index,i)){ 51 swap(a[i],a[index]); 52 Permutaion1(a,size,index+1); 53 swap(a[i],a[index]); 54 } 55 } 56 } 57 //有重复字符串的全排列递归算法，空间换时间 58 void Permutaion2(int* a,int size,int index){ 59 if(index == size-1){ 60 Print(a,size); 61 return; 62 } 63 int dup[256] = {0}; 64 for(int i=index;i<size;i++){ 65 if(dup[a[i]]==1) 66 continue; 67 dup[a[i]] = 1; 68 swap(a[i],a[index]); 69 Permutaion2(a,size,index+1); 70 swap(a[i],a[index]); 71 } 72 } 73 //字符串全排列非递归算法，求下一个排列的思想 74 void Reverse(int* from,int* to){ 75 int t; 76 while(from<to){ 77 t = *from; 78 *from = *to; 79 *to = t; 80 from++; 81 to --; 82 } 83 } 84 bool GetNextPermutation(int* a,int size){ 85 //后找，从后向前找最后一个升序的位置 86 int i = size-2; 87 while((i>=0)&&(a[i]>=a[i+1])) 88 i--; 89 if(i<0) return false; 90 //查找，从后面的元素中寻找比a[i]大的最小值a[j] 91 int j=size-1; 92 while(a[j]<=a[i]) 93 j--; 94 //交换 95 swap(a[i],a[j]); 96 //翻转 a[i+1...N-1] 97 Reverse(a+i+1,a+size-1); 98 return true; 99 } 100 int main() 101 { 102 int a[] = {1,2,3,4}; 103 cout<<"-----无重复字符串全排列递归算法-------"<<endl; 104 Permutaion(a,sizeof(a)/sizeof(int),0); 105 int a1[] = {1,2,2,3}; 106 cout<<"-----有重复字符串全排列递归算法-------"<<endl; 107 Permutaion1(a1,sizeof(a1)/sizeof(int),0); 108 cout<<"-----有重复字符串全排列递归算法(空间换时间)-------"<<endl; 109 Permutaion2(a1,sizeof(a1)/sizeof(int),0); 110 cout<<"-----字符串全排列非递归算法------------"<<endl; 111 int size = sizeof(a)/sizeof(int); 112 Print(a,size); 113 while(GetNextPermutation(a,size)) 114 Print(a,size); 115 return 0; 116 }
转载请注明出处：
C++博客园：godfrey_88