matching callback parameters in generic algorithm

[spakka]

I'm useless at templates, but, inspired by this post:

<hi***************************@syrcnyrdrs-01-ge0.nyroc.rr.com>,

I'm trying to write an algorithm

template <class BidirectionalIterator, class Function, class Size>
Function for_each_combination(BidirectionalIterator first,
BidirectionalIterator last,
Size k,
Function fn);

which does the obvious thing.

The post references some code (from Feb 05 CUJ) which implements
for_each_permutation. That implementation uses a nice algorithm from
Knuth to generate the permutations which

(i) cycles the elements of [first, last[ in situ, so that the callback can
be called simply as fn(first, last).

(ii) leaves the elements of [first, last[ in their original order.

I can't find such a nice algorithm for combinations. I have a simple
enough algorithm which generates all combinations of the integers 1, ...
(k-1). When it comes to calling the callback fn for each combination, I
copy the corresponding k elements from [first, last[ into a

vector<typename iterator_traits<BidirectionalIterator>::value_type >

but I can't make the call to fn. The caller supplies a callback taking
two parameters of the type BidirectionalIterator, which isn't matched.

My questions:

Is there a way that I can convert iterators from my vector into the type
of the template parameter BidirectionalIterator?

Alternatively, and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?

Thanks.

[spakka]

On Sat, 10 Sep 2005 12:24:48 +0000, spakka wrote:

Alternatively, and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?

Ok - sorted now.

[John Harrison]

spakka wrote:

On Sat, 10 Sep 2005 12:24:48 +0000, spakka wrote:

Alternatively, and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?

Ok - sorted now.

How? It was an interesting problem.

john

[spakka]

On Sun, 11 Sep 2005 13:29:49 +0000, John Harrison wrote:

spakka wrote:

On Sat, 10 Sep 2005 12:24:48 +0000, spakka wrote:

Alternatively, and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?

Ok - sorted now.

How? It was an interesting problem.

john

I cheated. I just copy into the storage that was passed to me, then
restore the original contents at the end:
// not for users
template<class ForwardIterator, class RandomAccessIterator,
class Size, class Function>
Function _combine(ForwardIterator first, ForwardIterator lastk,
ForwardIterator current, Size n, Size k, Size base, Size level,
Function f, RandomAccessIterator vals)
{
for (Size i = base; i < n - k + 1 + level; ++i) {
*current = vals[i];
if (level == k - 1) {
f(first, lastk);
}
else {
f = _combine(first, lastk, current + 1, n, k, i + 1, level + 1,
f, vals);
}
}
return f;
}

template<class ForwardIterator, class Function, class Size>
Function for_each_combination(ForwardIterator first,
ForwardIterator last, Size k, Function fn)
{
Size n = distance(first, last);
ForwardIterator lastk = first;
advance(lastk, k);

// save the original sequence
vector<typename iterator_traits<ForwardIterator>::value_type> sav;
sav.reserve(n);
copy(first, last, back_inserter(sav));

fn = _combine(first, lastk, first, n, k, 0, 0, fn, sav.begin());

// restore the original sequence
copy(sav.begin(), sav.end(), first);

return fn;
}