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

From: Ben Bear (benbearchen_at_[hidden])
Date: 2008-01-15 09:22:36

Phil, Hi!

Make them sorted, so we know more information about the input
sequence.  It's easy to find the max or min elements.  All those
lexicographical ordered algorithms have to find most greatest or
smallest needed element.

gacap provides three types interface:
- functions, like std::next_permutation
- direct classes, wrapper of functions
- indirect classes, work at the iterators but not the elements
directly, wrapper of classes direct.  I think this is like the
parallel index array.

Well, Herve' proposal may only contains part functions, but boost may
aceept more :-)

2007/1/16, Phil Garofalo <philgarofalo_at_[hidden]>:
> Ben, Apologies for the late response. I haven't run GACAP yet, but
> sorting the unselected elements sounds right. I am a bit surprised that
> keeping them sorted doesn't essentially have the same cost. Again, I
> will look at your implementation more closely.
>
> The parallel index array approach is describe in the book _Discrete
> Mathematics_ by Johnsonbaugh. It essentially creates an integer array of
> the same size as the input container as indexes into the container, and
> then sorts as appropriate through the integers (less costly
> comparisons). I didn't implement it because directly manipulating the
> container seems more elegant and not that much more costly.
>
> Regards,
>
> Phil
>
> Ben Bear wrote:
> > Philip:  Yeah, I think our methods are same.  Well, the unselected
> > elements are sorted makes the algorithm easy to be implemented and
> > more quicker.
> >
> > Sorry, I don't know what's parallel index array ;-(  I read the
> > defination of "Parallel array" in wikipedia... Does it like iterator
> > to iterator??
> >
> >
> > 2007/12/24, Philip Garofalo <philgarofalo_at_[hidden]>:
> >> Hello Ben and Herve, I'm not sure if you already know but there's a previous
> >> submission for combinations and permutations (mine) in the sequence_algo
> >> folder of the sandbox. In fact, Herve helped out! :-) I've been away from it
> >> for five years. Check out the discussion thread in the
> >> archives. Nevertheless, I like your implementation. It's interesting that
> >> you chose a sorting method similar to mine, instead of using a parallel
> >> index array.
> >>
> >> Phil Garofalo
> >>
> >> On Dec 23, 2007 7:38 PM, Ben Bear <benbearchen_at_[hidden]> wrote:
> >>
> >>> Sorry. I had lost too many times.
> >>>
> >>>
> >>> 2007/12/6, Hervé Brönnimann <hervebronnimann_at_[hidden]>:
> >>>> http://photon.poly.edu/~hbr/boost/combination.hpp
> >>> My test showed that a bug exists in prev_mapping().  The last sentence
> >>> of prev_mapping() should be "return false;", but not "return true;".
> >>> Date of the tested combination.hpp is 2007-12-6.
> >>>
> >>> I'll put my test tonight.  It mainly test the increment/decrement of
> >>> the sequences and the returned flags.
> >>> _______________________________________________
> >>> Unsubscribe & other changes:
> >>> http://lists.boost.org/mailman/listinfo.cgi/boost
> >>>
> >> _______________________________________________
> >> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> >>
> > _______________________________________________
> > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> >
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost