如何用非递归的算法来求解一个"全排列"

weichuang02

求一个数列的全排列，用递归的方法很容易描述，网上也有很多例子

但是如果要求必须不能用递归，可以用堆栈来求解，这个算法/代码应该如何描述呢? 我在纸上试了一下，没出来。

大家有什么思路么?

_Rayx

很容易啊，求一个排列的下一个排列是O（n）的算法。
很排好序，当作第一个排列，然后一直求下一个排序，直接没有下一个即可。

weichuang02

_Rayx 发表于 2012-09-02 15:31
很容易啊，求一个排列的下一个排列是O（n）的算法。
很排好序，当作第一个排列，然后一直求下一个排序，直 ...

能否稍微详细一点呢? 我想展开这个思路发现还是卡住了。

sacry

回复 3# weichuang02

关键字
lexicographic permutation 或者 next permutation


   

_Rayx

回复 3# weichuang02


    假设中间某一个排列是　１　３　４　５　９　７　２
它的下一个排列是１　３　４　７　２　５　９
其实就是发现２《7 7<9 9>5,于是找到比5大的最小数，7，交换变成1 3 4 7 9 5 2,再将7后面的数首尾交换，变成1 3 4 7 2 5 9
这样就是下一个排列了。

sacry

回复 5# _Rayx

假设中间某一个排列是　１　３　４　５　９　７　２
它的下一个排列是１　３　４　７　２　５　９
其实就是发现２《7 7<9 9>5,于是找到比5大的最小数，7，交换变成1 3 4 7 9 5 2,再将7后面的数首尾交换，变成1 3 4 7 2 5 9
这样就是下一个排列了。

这例子后半组正好3个数字，会让人误解的...
准确地说应该是reverse。
   

KanonInD

lexicographic permutation 用Python写的：http://en.wikipedia.org/wiki/Per ... lexicographic_order

1. def permutation(ls):
   
2.     length = len(ls)
   
3.     print(ls)
   
4.     while True:
   
5.         k = -1
   
6.         for i in range(length-1):
   
7.             if ls[i] < ls[i+1]:
   
8.                 k = i
   
9.         if k == -1:break
   
10.         l = 0
    
11.         for i in range(k,length):
    
12.             if ls[k] < ls[i]:
    
13.                 l = i
    
14.         ls[k],ls[l] = ls[l],ls[k]
    
15.         ls[k+1:] = ls[k+1:][::-1]
    
16.         print(ls)
    

复制代码

starwing83

http://yzfy.org/dis/listpost.php?tid=498&page=16#pid169692

_Rayx

回复 6# sacry


    you are right.

cjaizss

weichuang02 发表于 2012-09-02 15:28
求一个数列的全排列，用递归的方法很容易描述，网上也有很多例子

但是如果要求必须不能用递归，可以用堆 ...

正好之前写了个

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #include <stdlib.h>
   
5. 
   
6. int *flag;
   
7. 
   
8. void print(int*a,int num)
   
9. 
   
10. {
    
11. 
    
12.         int i;
    
13. 
    
14.         num--;
    
15. 
    
16.         for(i=0;i<num;i++)
    
17. 
    
18.                 printf("%d->",a[i]);
    
19. 
    
20.         printf("%d\n",a[num]);
    
21. 
    
22. }
    
23. 
    
24. 
    
25. 
    
26. int next(int*a,int m, int n,int how)
    
27. 
    
28. {
    
29. 
    
30.         int i,j,k,x;
    
31. 
    
32.         if(how) {
    
33. 
    
34.                 for(j=n-1;j>=0;j--) {
    
35. 
    
36.                         for(i=a[j];i<m;i++)
    
37. 
    
38.                                 if(flag[i]==0)
    
39. 
    
40.                                         break;
    
41. 
    
42.                         if(i<m) {
    
43. 
    
44.                                 flag[a[j]-1]=0;
    
45. 
    
46.                                 a[j]=i+1;
    
47. 
    
48.                                 flag[i]=1;
    
49. 
    
50. 
    
51. 
    
52.                                 for(x=0,k=j+1;k<n;k++) {
    
53. 
    
54.                                         while(flag[x]==1)x++;
    
55. 
    
56.                                         a[k]=x+1;
    
57. 
    
58.                                         flag[x]=1;
    
59. 
    
60.                                 }
    
61. 
    
62.                                 return 0;
    
63. 
    
64.                         }
    
65. 
    
66.                         flag[a[j]-1]=0;
    
67. 
    
68.                 }
    
69. 
    
70.         }
    
71. 
    
72.         else {
    
73. 
    
74.                 if(a[n-1]<m) {
    
75. 
    
76.                         a[n-1]++;
    
77. 
    
78.                         return 0;
    
79. 
    
80.                 }
    
81. 
    
82.                 for(i=n-1;i>0;i--)
    
83. 
    
84.                         if(a[i]>a[i-1]+1)
    
85. 
    
86.                                 break;
    
87. 
    
88.                 if(i>0) {
    
89. 
    
90.                         a[i-1]++;
    
91. 
    
92.                         for(;i<n;i++)
    
93. 
    
94.                                 a[i]=a[i-1]+1;
    
95. 
    
96.                         return 0;
    
97. 
    
98.                 }
    
99. 
    
100.         }
     
101. 
     
102.         return 1;
     
103. 
     
104. }
     
105. 
     
106. 
     
107. 
     
108. int main(int argc,char**argv)
     
109. 
     
110. {
     
111. 
     
112.         int *a,i;
     
113. 
     
114.         char c;
     
115. 
     
116.         int m,n;
     
117. 
     
118.         int how=0;
     
119. 
     
120.         c=argv[3][0];
     
121. 
     
122.         sscanf(argv[1],"%d",&m);
     
123. 
     
124.         sscanf(argv[2],"%d",&n);
     
125. 
     
126.         if(!(0<n&&n<=m)||(c!='P'&&c!='p'&&c!='C'&&c!='c'))
     
127. 
     
128.                 return 1;
     
129. 
     
130.         a = malloc(sizeof(int)*n);
     
131. 
     
132.         if(c=='P'||c=='p') {
     
133. 
     
134.                 how =1;
     
135. 
     
136.                 flag = malloc(sizeof(int)*m);
     
137. 
     
138.                 for(i=0;i<n;i++)
     
139. 
     
140.                         flag[i]=1;
     
141. 
     
142.                 for(;i<m;i++)
     
143. 
     
144.                         flag[i]=0;
     
145. 
     
146.         }
     
147. 
     
148.         if(a==NULL)
     
149. 
     
150.                 return 1;
     
151. 
     
152.         for(i=0;i<n;i++)
     
153. 
     
154.                 a[i]=i+1;
     
155. 
     
156.         while(1) {
     
157. 
     
158.                 print(a,n);
     
159. 
     
160.                 if(next(a,m,n,how))
     
161. 
     
162.                         return 0;
     
163. 
     
164.         }
     
165. 
     
166. }
     
167. 
     

复制代码