排列组合问题

doctorjxd

自定义的next_collection，呵呵。
效率比上面的代码有提高，结构又清晰。

doctorjxd

代码

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. #include <iterator>
   
6. #include <algorithm>
   
7. #include "combination.hpp" //这个文件的代码在下一个帖子，是老美的作品。
   
8. 
   
9. int main()
   
10. {
    
11.   using namespace std;
    
12.   using benbear::next_combination;
    
13.   typedef vector<char> vec_char;
    
14.   vec_char thestr;
    
15.   copy(istream_iterator<char>(cin),istream_iterator<char>(),back_insert_iterator<vec_char>(thestr));
    
16.   sort(thestr.begin(),thestr.end());
    
17.   for(int i=1;i<=thestr.size();i++)
    
18.   {
    
19.     do
    
20.     {
    
21.       do
    
22.       {
    
23.          copy(thestr.begin(),thestr.begin()+i,ostreambuf_iterator<char>(cout));
    
24.          cout << endl;
    
25.       } while(next_permutation(thestr.begin(),thestr.begin()+i));
    
26.     }while(next_combination(thestr.begin(),thestr.begin()+i,thestr.end()));
    
27.   }
    
28.   return 0;
    
29. }
    
30. 
    

复制代码

[ 本帖最后由 doctorjxd 于 2007-4-3 22:43 编辑 ]

doctorjxd

还是顺手把combination.hpp的内容给你贴上来吧。
是老美的作品。

1. 
   
2. 
   
3. // Combination algorithm implementation
   
4. 
   
5. // Copyright (C) 2004, BenBear
   
6. //
   
7. // This file is an algorithm of the combination. This library is free
   
8. // software; you can redistribute it and/or modify it under the terms
   
9. // of the GNU General Public License as published by the Free Software
   
10. // Foundation; either version 2, or (at your option) any later
    
11. // version.
    
12. 
    
13. // This library is distributed in the hope that it will be useful, but
    
14. // WITHOUT ANY WARRANTY; without even the implied warranty of
    
15. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    
16. // General Public License for more details.
    
17. 
    
18. // You should have received a copy of the GNU General Public License
    
19. // along with this library; see the file COPYING.  If not, write to
    
20. // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
    
21. // MA 02111-1307, USA.
    
22. 
    
23. #include <algorithm>
    
24. 
    
25. namespace benbear
    
26. {
    
27. 
    
28. using namespace std;
    
29. 
    
30. template <typename BiIterator>
    
31. void
    
32. sort_combination (BiIterator first, BiIterator last)
    
33. {
    
34.   if (first == last) // no element
    
35.     return;
    
36. 
    
37.   BiIterator i = first;
    
38.   ++i;
    
39.   if (i == last)     // one element
    
40.     return;
    
41.   
    
42.   int half = distance (first, last) / 2;  // half of the length
    
43.   BiIterator middle = first;
    
44.   advance (middle, half);  // middle += half
    
45. 
    
46.   sort_combination (first, middle);     // sort first part
    
47.   sort_combination (middle, last);      // sort second part
    
48. 
    
49.   inplace_merge (first, middle, last);  // merge two parts
    
50. }
    
51. 
    
52. template <typename BiIterator>
    
53. void
    
54. adjust_combination (BiIterator first, BiIterator middle, BiIterator last)
    
55. {
    
56.   // the front part or the back part have no elements
    
57.   if ((first == middle) || (middle == last))
    
58.     return;
    
59. 
    
60.   sort_combination (first, middle);
    
61.   sort_combination (middle, last);
    
62. 
    
63.   BiIterator b = middle;
    
64.   --b;
    
65.   BiIterator j = lower_bound (middle, last, *b);
    
66.   reverse (j, last);
    
67.   reverse (middle, last);
    
68. }
    
69. 
    
70. template <typename BiIterator>
    
71. void
    
72. init_combination (BiIterator first, BiIterator middle, BiIterator last,
    
73.     bool min)
    
74. {
    
75.   sort_combination (first, last);
    
76. 
    
77.   if (min == false)
    
78.     {
    
79.       // the max combination
    
80.       reverse (first, last);
    
81.       reverse (first, middle);
    
82.     }
    
83. }
    
84. 
    
85. template <typename BiIterator>
    
86. bool
    
87. next_combination (BiIterator first, BiIterator middle, BiIterator last)
    
88. {
    
89.   if ((first == middle) || (middle == last))
    
90.     return false;
    
91. 
    
92.   // last element of [first, middle)
    
93.   BiIterator b = middle;
    
94.   --b;
    
95. 
    
96.   if (*b < *middle)
    
97.     {
    
98.       BiIterator j = b;
    
99.       while ((++b != last) && (*j < *b))
    
100. {
     
101.    iter_swap (j, b);
     
102.    j = b;
     
103. }
     
104.       return true;
     
105.     }
     
106. 
     
107.   BiIterator e = last;
     
108.   --e;
     
109.   while (e != middle)
     
110.     {
     
111.       BiIterator k = e;
     
112.       --k;
     
113.       if (!(*k < *e))
     
114. e = k;
     
115.       else
     
116. break;
     
117.     }
     
118.   
     
119.   BiIterator f = e;
     
120.   ++f;
     
121.   while ((f != last) && !(*f < *e))
     
122.     ++f;
     
123. 
     
124.   if (!(*first < *e))
     
125.     {
     
126.       reverse (first, middle);
     
127.       reverse (first, last);
     
128.       return false;
     
129.     }
     
130. 
     
131.   if (*b < *e)
     
132.     {
     
133.       BiIterator bb = b;
     
134.       while ((++bb != e) && !(*b < *bb))
     
135. ;
     
136.       reverse (bb, f);
     
137.       reverse (b, f);
     
138.     }
     
139.   else
     
140.     {
     
141.       BiIterator i = b;
     
142.       while (!(*--i < *e))
     
143. ;
     
144.       
     
145.       BiIterator j = last;
     
146.       while (!(*i < *--j))
     
147. ;
     
148. 
     
149.       iter_swap (i, j);
     
150.       reverse (++i, middle);
     
151.       reverse (i, j);
     
152.     }
     
153.   return true;
     
154. }
     
155. 
     
156. template <typename BiIterator>
     
157. bool
     
158. prev_combination (BiIterator first, BiIterator middle, BiIterator last)
     
159. {
     
160.   if ((first == middle) || (middle == last))
     
161.     return false;
     
162.   
     
163.   BiIterator b = middle;
     
164.   --b;
     
165.   
     
166.   if (*middle < *b)
     
167.     {
     
168.       BiIterator i = upper_bound (first, middle, *middle);
     
169.       if (i != b)
     
170. iter_swap (i, middle);
     
171.       else
     
172. {
     
173.    BiIterator s = middle;
     
174.    while ((++s != last) && !(*s < *middle))
     
175.      ;
     
176.    reverse (b, s);
     
177. }
     
178. 
     
179.       return true;
     
180.     }
     
181.   
     
182.   BiIterator e = last;
     
183.   --e;
     
184.   while (e != middle)
     
185.     {
     
186.       BiIterator k = e;
     
187.       --k;
     
188.       if (!(*k < *e))
     
189. e = k;
     
190.       else
     
191. break;
     
192.     }
     
193.   
     
194.   BiIterator f = e;
     
195.   ++f;
     
196.   while ((f != last) && !(*f < *e))
     
197.     ++f;
     
198. 
     
199.   if (f == last)
     
200.     {
     
201.       reverse (first, last);
     
202.       reverse (first, middle);
     
203.       return false;
     
204.     }
     
205. 
     
206.   BiIterator i = upper_bound (first, middle, *f);
     
207.   if (i == b)
     
208.     {
     
209.       BiIterator s = f;
     
210.       while ((++s != last) && !(*s < *f))
     
211. ;
     
212. 
     
213.       reverse (b, f);
     
214.       reverse (b, s);
     
215.     }
     
216.   else
     
217.     {
     
218.       iter_swap (i, f);
     
219.       reverse (++i, f);
     
220.       reverse (i, middle);
     
221.     }
     
222.   return true;
     
223. }
     
224. 
     
225. } // end of namespace benbear
     
226. 
     
227. 
     
228. 
     

复制代码

doctorjxd

自己理解最深入的语言就是效率最高的语言。
自己一知半解，写一条语句都要费半天力的语言就是效率最低的语言。

doctorjxd

没有必要为语言的优劣而争论。

语言没有差别，
差别产生于不同人不同的理解。

世间的事物绝大多数都不能用好与坏来简单区分。但不同的人基于不同的立场，都会有不同的结论。

doctorjxd

本贴有可能变成水贴，呵呵。

doctorjxd

不宜继续扯下去。

[ 本帖最后由 doctorjxd 于 2007-4-5 10:26 编辑 ]