RE: [boost] next_combination suggested addition to algorithm library

From: j.adelman_at_[hidden]
Date: 2002-04-24 04:23:36

Quoting j.adelman_at_[hidden]:

> Whoops!  Yes there is a bug in the testing code 
> (i.e. in the main function).  I'm not sure why 
> you appear to think that the line 
> while(*sp++=*tp); 
> can go wrong in two ways.  Walking of the end 
and 
> sp==se are the same thing...  Nevertheless, I 
> should check for weirdness in the user input, 
> i.e. the target does not contain a valid, 
sorted 
> combination from the source.  Fix below.  The 
> std::invalid_argument could be caught in 
> next_combination, and made to give the first 
> valid combination, perhaps, if this is what 
> anyone wants.
> 
> jsa
> 
> Quoting "Powell, Gary" <powellg_at_[hidden]>:
> 
> > 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;
do {
> if(sp==se) throw std::invalid_argument("second 
> sequence passed to next_combination() is not an 
> ordered subset of the first sequence");
> // is all that is needed to fix this.
}
> >   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
> > 
_______________________________________________
> > Unsubscribe & other changes:
> > 
> 
http://lists.boost.org/mailman/listinfo.cgi/boost
> > 
> 
> 
> ------------------------------------------------
-
> This mail sent through UK Online webmail
> _______________________________________________
> Unsubscribe & other changes:
> 
http://lists.boost.org/mailman/listinfo.cgi/boost
> 

-------------------------------------------------
This mail sent through UK Online webmail