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@gmail.com>:
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@gmail.com>:
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@gmail.com> wrote:
Sorry. I had lost too many times.
2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:
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