RE: [boost] next_combination suggested addition to algorithm library

From: Powell, Gary (powellg_at_[hidden])
Date: 2002-04-23 12:32:09

looks cool, but has  bug.
  -Gary-

-----Original Message-----
From: James S. Adelman [mailto:j.adelman_at_[hidden]] 
Sent: Saturday, April 20, 2002 3:59 PM
To: boost_at_[hidden]
Subject: [boost] next_combination suggested addition to algorithm
library

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);       <<===== If never matches will walk off the
end of sp. (Also no test for sp == se)
  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()) <<===
(?next_combination??)
  {
 
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
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost