OverSim
combination.h
Go to the documentation of this file.
1 // This source code is licensed under The Code Project Open License (CPOL)
2 // see http://www.codeproject.com/KB/recipes/CombC.aspx
3 //=======================================================
4 // combination.h
5 // Description : Template class to find combinations
6 //=======================================================
7 // Copyright 2003 - 2006 Wong Shao Voon
8 // No warranty, implied or expressed, is included.
9 // Author is not liable for any type of loss through
10 // the use of this source code. Use it at your own risk!
11 //=======================================================
12 
13 
14 #ifndef __COMBINATION_H__
15 #define __COMBINATION_H__
16 
17 
18 namespace oversim
19 {
20 
21 // Non recursive template function
22 template <class BidIt>
23 
24 inline bool next_combination(BidIt n_begin, BidIt n_end,
25 BidIt r_begin, BidIt r_end)
26 {
27 
28  bool boolmarked=false;
29  BidIt r_marked;
30 
31  BidIt n_it1=n_end;
32  --n_it1;
33 
34 
35  BidIt tmp_r_end=r_end;
36  --tmp_r_end;
37 
38  for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1)
39  {
40  if(*r_it1==*n_it1 )
41  {
42  if(r_it1!=r_begin) //to ensure not at the start of r sequence
43  {
44  boolmarked=true;
45  r_marked=(--r_it1);
46  ++r_it1;//add it back again
47  continue;
48  }
49  else // it means it is at the start the sequence, so return false
50  return false;
51  }
52  else //if(*r_it1!=*n_it1 )
53  {
54  //marked code
55  if(boolmarked==true)
56  {
57  //for loop to find which marked is in the first sequence
58  BidIt n_marked;//mark in first sequence
59  for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
60  if(*r_marked==*n_it2) {n_marked=n_it2;break;}
61 
62 
63  BidIt n_it3=++n_marked;
64  for (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
65  {
66  *r_it2=*n_it3;
67  }
68  return true;
69  }
70  for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
71  if(*r_it1==*n_it4)
72  {
73  *r_it1=*(++n_it4);
74  return true;
75  }
76  }
77  }
78 
79  return true;//will never reach here
80 }
81 
82 // Non recursive template function with Pred
83 template <class BidIt, class Prediate>
84 
85 inline bool next_combination(
86  BidIt n_begin,
87  BidIt n_end,
88  BidIt r_begin,
89  BidIt r_end,
90  Prediate Equal)
91 {
92 
93  bool boolmarked=false;
94  BidIt r_marked;
95 
96  BidIt n_it1=n_end;
97  --n_it1;
98 
99 
100  BidIt tmp_r_end=r_end;
101  --tmp_r_end;
102 
103  for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1)
104  {
105  if( Equal( *r_it1, *n_it1) )
106  {
107  if(r_it1!=r_begin) //to ensure not at the start of r sequence
108  {
109  boolmarked=true;
110  r_marked=(--r_it1);
111  ++r_it1;//add it back again
112  continue;
113  }
114  else // it means it is at the start the sequence, so return false
115  return false;
116  }
117  else //if(*r_it1!=*n_it1 )
118  {
119  //marked code
120  if(boolmarked==true)
121  {
122  //for loop to find which marked is in the first sequence
123  BidIt n_marked;//mark in first sequence
124  for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
125  if( Equal( *r_marked, *n_it2) ) {n_marked=n_it2;break;}
126 
127 
128  BidIt n_it3=++n_marked;
129  for (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
130  {
131  *r_it2=*n_it3;
132  }
133  return true;
134  }
135  for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
136  if( Equal(*r_it1, *n_it4) )
137  {
138  *r_it1=*(++n_it4);
139  return true;
140  }
141  }
142  }
143 
144  return true;//will never reach here
145 }
146 
147 
148 // Non recursive template function
149 template <class BidIt>
150 
151 inline bool prev_combination(BidIt n_begin, BidIt n_end,
152 BidIt r_begin, BidIt r_end)
153 {
154 
155  bool boolsame=false;
156  BidIt marked;//for r
157  BidIt r_marked;
158  BidIt n_marked;
159 
160 
161  BidIt tmp_n_end=n_end;
162  --tmp_n_end;
163 
164  BidIt r_it1=r_end;
165  --r_it1;
166 
167  for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1)
168  {
169  if(*r_it1==*n_it1)
170  {
171  r_marked=r_it1;
172  n_marked=n_it1;
173  break;
174  }
175  }
176 
177  BidIt n_it2=n_marked;
178 
179 
180  BidIt tmp_r_end=r_end;
181  --tmp_r_end;
182 
183  for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2)
184  {
185  if(*r_it2==*n_it2 )
186  {
187  if(r_it2==r_begin&& !(*r_it2==*n_begin) )
188  {
189  for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3)
190  {
191  if(*r_it2==*n_it3)
192  {
193  marked=r_it2;
194  *r_it2=*(--n_it3);
195 
196  BidIt n_it4=n_end;
197  --n_it4;
198  for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4)
199  {
200  *r_it3=*n_it4;
201  }
202  return true;
203  }
204  }
205  }
206  else if(r_it2==r_begin&&*r_it2==*n_begin)
207  {
208  return false;//no more previous combination;
209  }
210  }
211  else //if(*r_it2!=*n_it2 )
212  {
213  ++r_it2;
214  marked=r_it2;
215  for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5)
216  {
217  if(*r_it2==*n_it5)
218  {
219  *r_it2=*(--n_it5);
220 
221  BidIt n_it6=n_end;
222  --n_it6;
223  for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6)
224  {
225  *r_it4=*n_it6;
226  }
227  return true;
228  }
229  }
230  }
231  }
232  return false;//Will never reach here, unless error
233 }
234 
235 
236 // Non recursive template function with Pred
237 template <class BidIt, class Prediate>
238 
239 inline bool prev_combination(
240  BidIt n_begin,
241  BidIt n_end,
242  BidIt r_begin,
243  BidIt r_end,
244  Prediate Equal)
245 {
246 
247  bool boolsame=false;
248  BidIt marked;//for r
249  BidIt r_marked;
250  BidIt n_marked;
251 
252 
253  BidIt tmp_n_end=n_end;
254  --tmp_n_end;
255 
256  BidIt r_it1=r_end;
257  --r_it1;
258 
259  for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1)
260  {
261  if( Equal(*r_it1, *n_it1) )
262  {
263  r_marked=r_it1;
264  n_marked=n_it1;
265  break;
266  }
267  }
268 
269  BidIt n_it2=n_marked;
270 
271 
272  BidIt tmp_r_end=r_end;
273  --tmp_r_end;
274 
275  for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2)
276  {
277  if( Equal(*r_it2, *n_it2) )
278  {
279  if(r_it2==r_begin&& !Equal(*r_it2, *n_begin) )
280  {
281  for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3)
282  {
283  if(Equal(*r_it2, *n_it3))
284  {
285  marked=r_it2;
286  *r_it2=*(--n_it3);
287 
288  BidIt n_it4=n_end;
289  --n_it4;
290  for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4)
291  {
292  *r_it3=*n_it4;
293  }
294  return true;
295  }
296  }
297  }
298  else if(r_it2==r_begin&&Equal(*r_it2, *n_begin))
299  {
300  return false;//no more previous combination;
301  }
302  }
303  else //if(*r_it2!=*n_it2 )
304  {
305  ++r_it2;
306  marked=r_it2;
307  for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5)
308  {
309  if(Equal(*r_it2, *n_it5))
310  {
311  *r_it2=*(--n_it5);
312 
313  BidIt n_it6=n_end;
314  --n_it6;
315  for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6)
316  {
317  *r_it4=*n_it6;
318  }
319  return true;
320  }
321  }
322  }
323  }
324  return false;//Will never reach here, unless error
325 }
326 
327 
328 // Recursive template function
329 template <class RanIt, class Func>
330 
331 void recursive_combination(RanIt nbegin, RanIt nend, int n_column,
332  RanIt rbegin, RanIt rend, int r_column,int loop, Func func)
333 {
334 
335  int r_size=rend-rbegin;
336 
337 
338  int localloop=loop;
339  int local_n_column=n_column;
340 
341  //A different combination is out
342  if(r_column>(r_size-1))
343  {
344  func(rbegin,rend);
345  return;
346  }
348 
349  for(int i=0;i<=loop;++i)
350  {
351 
352  RanIt it1=rbegin;
353  for(int cnt=0;cnt<r_column;++cnt)
354  {
355  ++it1;
356  }
357 
358  RanIt it2=nbegin;
359  for(int cnt2=0;cnt2<n_column+i;++cnt2)
360  {
361  ++it2;
362  }
363 
364  *it1=*it2;
365 
366  ++local_n_column;
367 
368  recursive_combination(nbegin,nend,local_n_column,
369  rbegin,rend,r_column+1,localloop,func);
370  --localloop;
371  }
372 
373 }
374 
375 }
376 
377 #endif