# Boost :

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

looks cool, but has bug.
-Gary-

-----Original Message-----
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