12,076,727 members (44,290 online)

216.3K views
58 bookmarked
Posted

# Combinations in C++

, 13 Sep 2009 CPOL
An article on finding combinations.
 combination.zip combination testcombo.zip testcombo TestCombo res TestCombo.ico TestCombo.dsp TestCombo.dsw ```//======================================================= // combination.h // Description : Template class to find combinations //======================================================= // Copyright 2003 - 2006 Wong Shao Voon // No warranty, implied or expressed, is included. // Author is not liable for any type of loss through // the use of this source code. Use it at your own risk! //======================================================= #ifndef __COMBINATION_H__ #define __COMBINATION_H__ namespace stdcomb { // Non recursive template function template inline bool next_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) { bool boolmarked=false; BidIt r_marked; BidIt n_it1=n_end; --n_it1; BidIt tmp_r_end=r_end; --tmp_r_end; for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1) { if(*r_it1==*n_it1 ) { if(r_it1!=r_begin) //to ensure not at the start of r sequence { boolmarked=true; r_marked=(--r_it1); ++r_it1;//add it back again continue; } else // it means it is at the start the sequence, so return false return false; } else //if(*r_it1!=*n_it1 ) { //marked code if(boolmarked==true) { //for loop to find which marked is in the first sequence BidIt n_marked;//mark in first sequence for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2) if(*r_marked==*n_it2) {n_marked=n_it2;break;} BidIt n_it3=++n_marked; for (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3) { *r_it2=*n_it3; } return true; } for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4) if(*r_it1==*n_it4) { *r_it1=*(++n_it4); return true; } } } return true;//will never reach here } // Non recursive template function with Pred template inline bool next_combination( BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end, Prediate Equal) { bool boolmarked=false; BidIt r_marked; BidIt n_it1=n_end; --n_it1; BidIt tmp_r_end=r_end; --tmp_r_end; for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1) { if( Equal( *r_it1, *n_it1) ) { if(r_it1!=r_begin) //to ensure not at the start of r sequence { boolmarked=true; r_marked=(--r_it1); ++r_it1;//add it back again continue; } else // it means it is at the start the sequence, so return false return false; } else //if(*r_it1!=*n_it1 ) { //marked code if(boolmarked==true) { //for loop to find which marked is in the first sequence BidIt n_marked;//mark in first sequence for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2) if( Equal( *r_marked, *n_it2) ) {n_marked=n_it2;break;} BidIt n_it3=++n_marked; for (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3) { *r_it2=*n_it3; } return true; } for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4) if( Equal(*r_it1, *n_it4) ) { *r_it1=*(++n_it4); return true; } } } return true;//will never reach here } // Non recursive template function template inline bool prev_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) { bool boolsame=false; BidIt marked;//for r BidIt r_marked; BidIt n_marked; BidIt tmp_n_end=n_end; --tmp_n_end; BidIt r_it1=r_end; --r_it1; for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1) { if(*r_it1==*n_it1) { r_marked=r_it1; n_marked=n_it1; break; } } BidIt n_it2=n_marked; BidIt tmp_r_end=r_end; --tmp_r_end; for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2) { if(*r_it2==*n_it2 ) { if(r_it2==r_begin&& !(*r_it2==*n_begin) ) { for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3) { if(*r_it2==*n_it3) { marked=r_it2; *r_it2=*(--n_it3); BidIt n_it4=n_end; --n_it4; for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4) { *r_it3=*n_it4; } return true; } } } else if(r_it2==r_begin&&*r_it2==*n_begin) { return false;//no more previous combination; } } else //if(*r_it2!=*n_it2 ) { ++r_it2; marked=r_it2; for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5) { if(*r_it2==*n_it5) { *r_it2=*(--n_it5); BidIt n_it6=n_end; --n_it6; for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6) { *r_it4=*n_it6; } return true; } } } } return false;//Will never reach here, unless error } // Non recursive template function with Pred template inline bool prev_combination( BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end, Prediate Equal) { bool boolsame=false; BidIt marked;//for r BidIt r_marked; BidIt n_marked; BidIt tmp_n_end=n_end; --tmp_n_end; BidIt r_it1=r_end; --r_it1; for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1) { if( Equal(*r_it1, *n_it1) ) { r_marked=r_it1; n_marked=n_it1; break; } } BidIt n_it2=n_marked; BidIt tmp_r_end=r_end; --tmp_r_end; for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2) { if( Equal(*r_it2, *n_it2) ) { if(r_it2==r_begin&& !Equal(*r_it2, *n_begin) ) { for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3) { if(Equal(*r_it2, *n_it3)) { marked=r_it2; *r_it2=*(--n_it3); BidIt n_it4=n_end; --n_it4; for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4) { *r_it3=*n_it4; } return true; } } } else if(r_it2==r_begin&&Equal(*r_it2, *n_begin)) { return false;//no more previous combination; } } else //if(*r_it2!=*n_it2 ) { ++r_it2; marked=r_it2; for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5) { if(Equal(*r_it2, *n_it5)) { *r_it2=*(--n_it5); BidIt n_it6=n_end; --n_it6; for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6) { *r_it4=*n_it6; } return true; } } } } return false;//Will never reach here, unless error } // Recursive template function template void recursive_combination(RanIt nbegin, RanIt nend, int n_column, RanIt rbegin, RanIt rend, int r_column,int loop, Func func) { int r_size=rend-rbegin; int localloop=loop; int local_n_column=n_column; //A different combination is out if(r_column>(r_size-1)) { func(rbegin,rend); return; } ///////////////////////////////// for(int i=0;i<=loop;++i) { RanIt it1=rbegin; for(int cnt=0;cnt

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

## Share

 Software Developer (Senior) Singapore
IT Certifications

• IT Infrastructure Library Foundational (ITIL v3)
• Scrum Alliance Certified Scrum Master (CSM)
• EC-Council Certified Secure Programmer (ECSP) .NET
• EC-Council Certified Ethical Hacker (CEH)
• EC-Council Certified Security Analyst (ECSA)
• Certified Secure Software Lifecycle Professional (CSSLP)