[boost] next_combination suggested addition to algorithm library

From: James S. Adelman (j.adelman_at_[hidden])
Date: 2002-04-20 17:59:28

Since there is next_permutation, why not next_combination?  It looks like 
this:

template <typename SrcIt, typename TrgIt>
bool next_combination_helper(SrcIt sp,SrcIt se,TrgIt tp,TrgIt te) 
{
  if(tp==te) return false;
  while(*sp++!=*tp); 
  TrgIt tq=tp; ++tq;
  if(next_combination_helper(sp,se,tq,te)) return true;
  for(;;)
  {
    if (sp==se) return false; // overflow
    *tp++=*sp++;
    if (tp==te) return true;
  }
}

template <typename SrcIt, typename TrgIt>
bool next_combination(SrcIt sb,SrcIt se,TrgIt tb,TrgIt te)
{
  if(next_combination_helper(sb,se,tb,te)) return true;
  for(;tb!=te;*tb++=*sb++);
  return false;
}

// Example usage:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
  int arr[6]={1,2,3,4,5,6};
  std::vector v(arr,arr+6);
  std::vector w(v.begin(),v.begin()+3);
  while(next_permutation(v.begin(),v.end(),w.begin(),w.end())
  {
     std::copy(w.begin(),w.end(),std::ostream_iterator<int>(std::cout,"\t"));
     std::cout<<std::endl;
  }
}

It can probably be optimised for bidirectional and random-access iterators, 
but this version requires only that the iterators be copyable.

James