Re: [boost] [gacap]Is any interesting to "Generating All Combinations and Permutations"？

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