From fcc8f4bd8eb81cb5d4a1713b478e82baee977eda Mon Sep 17 00:00:00 2001 From: APTX Date: Thu, 15 Dec 2011 21:20:53 +0100 Subject: [PATCH] Add "combinatorics library". --- combination.h | 375 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 375 insertions(+) create mode 100644 combination.h diff --git a/combination.h b/combination.h new file mode 100644 index 0000000..630f6a2 --- /dev/null +++ b/combination.h @@ -0,0 +1,375 @@ +//======================================================= +// 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