RE: [boost] next_combination suggested addition to algorithm library

From: j.adelman_at_[hidden]
Date: 2002-04-23 13:49:07

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;

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