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

From: Ben Bear (benbearchen_at_[hidden])
Date: 2007-11-13 08:39:29

I put a implementation in:
http://www.bxmy.org/combi/combination.hpp
only contains "Without repetition" functions.  And I'll write an example.

The partial_permutation is so simple, so it's should be very solid.
We can test combinations using partial_permutation.  Because
partial_permutation(first, middle, last)'s results contain all
combination(first, middle, last)'s results, and if
partial_permutation's [first, middle) is like sorted, it's a
combinatin.  I had do this test.

A interesting of combination.  We can define ONE function to replace
next_ and prev_combination, that is:

bool combiantion(BiIter selected_first, BiIter selected_last,
                         BiIter unselected_first, BiIter unselected_last);

Now, next_combination(first, middle, last) equal combination(first,
middle, middle, last).
And prev_combination(first, middle, last) equal combination(middle,
last, first, middle).

I'm sorry.  I just can't understand your combinations and permutations
with repetitions.  I need time to think about this.  But I think your
idea is good :-)

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:
> >>
> >> http://photon.poly.edu/~hbr/boost/combinations.html
> >>
> >> 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
>