非递归全排列

非递归全排列无非就是根据一个排列找到下一个；
以1 2 3 4 为例子；
1：先把给定的字符串排序（于小到大）；
2：从后到前找到第一个相邻的递增对；例如：1 2 4 3 找到2 4 递增 于是得到4的下标2；如果没有找到，说明已经全排列好了；直接退出；
3：然后从后向前找到第一个比 2 大的值， 即 3；
4：交换2 3；—->1 3 4 2;
5:在从4(第2不的得到的4 下标) 开始早最后 逆序—->1 3 2 4；
6：重复2-5步骤；

如果您有更好的方法请留言，谢谢！！！

#include<iostream>
#include<list>
using namespace std;

//交换函数
void Swap(char *a, char *b)

{ char tmp = *a; *a = *b; *b = tmp;
}


//逆序函数
void Reverse(char arr[] , int k)
{ if(arr==NULL || k<0 || k>strlen(arr)-1) { return; } int len  = strlen(arr); int i=0; int j=0; for(i = k, j =len-1; i<=j;++i, --j) { Swap(arr+i , arr+j); }
}

//全排列
void _Perm(char arr[])
{ if(arr == NULL) //控制参数的正确性 { return; } int len = strlen(arr); if(len<=2) { return; } while(1)//重复 { cout<<arr<<endl; int i=0; int j=0; for(i=len-2; i>=0; --i) //步骤2 { if(arr[i]<arr[i+1]) //招不符合规则的第一个 { break; } else if(i==0) { return; } } for(j=len-1; j>i;--j) //找到要交换的下标  步骤3 { if(arr[j]>arr[i]) { break; } } Swap(arr+i, arr+j);  //步骤4 Reverse(arr,i+1); //步骤5 }
}

int main()
{ char arr[] = "2314"; char brr[] = "2314"; list<char> ls ; for(int i=0;brr[i] !='\0';++i) { ls.push_back(brr[i]); } ls.sort();//排序 list<char>::iterator lr = ls.begin(); for(int i=0; lr != ls.end() ;++lr,++i) { arr[i] = *lr; } _Perm(arr); return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
 

文章来源: blog.csdn.net，作者：IM-STONE，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/doubleintfloat/article/details/52198846