Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Combinations in C++

, 13 Sep 2009 CPOL
An article on finding combinations.
//=======================================================
// combination.h
// Description : Template class to find combinations
//=======================================================
// Copyright 2003 - 2005 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 <class BidIt>

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 <class BidIt, class Prediate>

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 <class BidIt>

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 <class BidIt, class Prediate>

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 <class RanIt, class Func>

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<r_column;++cnt)
		{
		  ++it1;
		} 
		
		RanIt it2=nbegin;
		for(int cnt2=0;cnt2<n_column+i;++cnt2)
		{
		  ++it2;
		} 
		
		*it1=*it2;
		
		++local_n_column;
		
		recursive_combination(nbegin,nend,local_n_column,
		        rbegin,rend,r_column+1,localloop,func);
		--localloop;
	}
	
}

}

#endif

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Shao Voon Wong
Software Developer
Singapore Singapore
No Biography provided

| Advertise | Privacy | Mobile
Web01 | 2.8.141022.2 | Last Updated 13 Sep 2009
Article Copyright 2003 by Shao Voon Wong
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid