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

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.

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
>