Boost :

From: Ben Bear (benbearchen_at_[hidden])
Date: 2007-11-13 12:10:55

I think, I know what you want to do with this function:

template <class BidirectionalIterator>
bool
next_permutation(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value);

I wrote a implementation, and found that it's easy :-)

template <typename BiIter, typename T>
bool
next_repeat_permutation (BiIter first, BiIter last,
T first_value, T last_value)
{
if (first == last)
return false;

BiIter end = last;

while (end != first)
{
BiIter bi = end;
--bi;
T& t = ++*bi;
if (t != last_value)
break;

end = bi;
}

std::fill (end, last, first_value);

return end != first;
}

Oh, your idia is beautiful :p

I think that calling this function `next_permutation' is not good.
It's very different from std::next_permutation. My
`next_repeat_permutation' is also not a good name, because only I call
it `repeat_permutation'.

Another, repetitions combination:

template <typename BiIter, typename T>
bool
next_repeat_combination (BiIter first, BiIter last,
T first_value, T last_value)
{
if (first == last)
return false;

BiIter end = last;

T f = first_value;

while (end != first)
{
BiIter bi = end;
--bi;
T& t = ++*bi;
if (t != last_value)
{
f = t;
break;
}

end = bi;
}

std::fill (end, last, f);

return end != first;
}

2007/11/13, Hervé Brönnimann <hervebronnimann_at_[hidden]>:
> Ben: Good, we have half the work agreed, then. There is no way you
> will be able to make classes into a a standard, it is too heavy
> compared to a single free-standing function. This is an extension,
> and not a very important one, so it stands best chance for
> standardization if it is lightweight, crisp, and still remains
> useful. I also don't see what classes bring that is so much better
> than free functions.
>
> And after thinking a bit, I came to the conclusion that providing the
> assignments from [first, last) to values in [first_value, last_value)
> for permutations with repetitions, and multiplicities for
> combinations with repetitions, was the best representation for the
> input/output. The user can use those to actually produce the
> permutations and combinations, i.e. replacing the value (iterator or
> integral index) by their elements pointed to in some input sequence,
> or copying the elements with the appropriate multiplicity, but it
> does away with a lot of things and simplifies the functions while
> retaining the core functionality. Doing otherwise would impose
> constraints such as CopyConstructible and Assignable for the elements
> of the combinations, sorted input range and EqualityComparable, etc.
> Not quite clear what you would do also with elements not present in
> some combination (multiplicity 0), but that would become present in
> the next combination. Etc.
>
> Hope that helps. I'm committed now to reach the best state for this
> proposal, so don't be shy criticizing my proposal. If I can't defend
> the arguments or you have a better position, I'll be very happy that
> we can improve on it!
> --HB
>
> Let me continue to improve the proposal, and provide examples. I
>
> On Nov 13, 2007, at 3:33 AM, Ben Bear wrote:
>
> > 2007/11/13, Hervé Brönnimann <hervebronnimann_at_[hidden]>:
> >> Ben: Before you do any substantial work, please check my proposal. I
> >> have tried to provide background / explanations, and a set of
> >> coherent interfaces. Please look at:
> >>

> >>
> >> The code in the .hpp (linked) is only temporary and not debugged. I
> >> am in the process of writing test cases. I'm happy to send it to you
> >> too... Keep in mind it is work in progress. I have a job and am
> >> spending far too much time on this at the moment :)
> >> --HB
> >>
> >> PS: I am not sure about the Incrementor/Decrementor interfaces,
> >> unless I can come up with a convincing example where the underlying
> >> type is not int and does not have operator++ and operator--, but it
> >> still makes sense to count with it...
> >>
> >
> > I agree with the eight "Without repetition" functions.
> >
> > But the "With Repetition", I think that providing classes, such as
> > class gacap::repeat_permutation, is better than functions. I had not
> > thought how to privide functions about repetition version. It's new
> > thing to me.
> >
> > I'll read this proposal. It's a little long for me.
> > _______________________________________________
> > Unsubscribe & other changes: http://lists.boost.org/mailman/
> > listinfo.cgi/boost
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>