Boost logo

Boost :

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-11-13 21:45:30


Ben:

On Nov 13, 2007, at 12:10 PM, Ben Bear wrote:
> 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 :-)

In the page I whose link I gave you, that has the documentation, I
guess you didn't try to click on the link named combination.hpp. I
should have pointed out that the code was available. My
implementation is the same in principle, but with fewer redundant
tests and assignments:

template <class BidirectionalIterator, class T>
   bool
   next_permutation(BidirectionalIterator first,
BidirectionalIterator last, T first_value, T last_value)
{
     while (last != first && ++(*(--last)) == last_value) {
         *last = first_value;
     }
     return last != first;
}

As for combinations, it's not much more complicated:

template <class BidirectionalIterator>
   bool
   next_combination(BidirectionalIterator first,
BidirectionalIterator last)
{
     BidirectionalIterator current = last;
     while (current != first && *(--current) == 0) {
     }
     if (current != first) {
         *(--last) = --(*current);
         ++*(--current);
     }
     return current != first;
}

> [snip]
> Oh, your idia is beautiful :p

Glad you like it. It's simple things that work best for me :)

> 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'.

The question of names is a good one. There is room for rationales,
in the documentation page: I would have put something there about
using the same name. There is no "partial" about it, this time, and
I didn't have any problems naming it permutations since the
signatures can't possibly be ambiguous. But perhaps a different name
is a good idea.

At heart, it's an assignment of values from [first,last) to
[first_value, last_value). So next_assignment would be a
possibility. Also since the relationship is functional,
next_function or next_mapping would be possible.
next_one_to_many_assignment or next_one_to_many_mapping is more
precise, but too long IMHO. I don't really like any of those
alternatives. It's a permutation with repetitions, but
next_repetition or next_permutation_with_repetition isn't good either...

In the end, I don't have anything better than next_permutation.
let's hear some more suggestions...

--
HB

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk