From: Phil Garofalo (philgarofalo_at_[hidden])
Date: 2008-01-14 23:07:36
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.
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]>:
>>> 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:
>> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk