[Newbies] Re: Another extension proposal -> subsets

[Klaus D. Witzel]

On Thu, 24 Jul 2008 20:09:53 +0200, Zulq Alam wrote:

> Klaus D. Witzel wrote:
>
>> Squeak looks to be already fast in this case, your routine is almost  
>> optimal :) Implementing it in Set so that Set's internal can be of  
>> benefit won't bring these figures down much -- what remains is (aSet  
>> includes: another), times #copyWithout: loop, and that seems to be  
>> unavoidable.
>
> It's significantly faster with a more appropriate hashing function:
>
> {2->0 . 3->0 . 4->1 . 5->1 . 6->3 . 7->9 . 8->22 . 9->59 . 10->138 .  
> 11->305 . 12->686 . 13->1640 . 14->4366 . 15->10550 . 16->28104 .  
> 17->93373 . 18->303425}

This is very good for small n :)

> combinations
>    | combinations |
>    combinations := (PluggableSet new: (2 raisedTo: self size))
>      hashBlock:
>        [:aSet |
>        aSet
>          inject: aSet size
>          into: [:hash :each | hash * each hash + each]];
>      yourself.
>    self combinationsInto: combinations.
>    ^ combinations
>
> combinationsInto: aSet
>    (aSet includes: self) ifTrue: [^ self].
>    aSet add: self.
>    self do:
>      [:each |
>      (self copyWithout: each) combinationsInto: aSet].	
>
> I think the problem is that most of the sets contain similar data so the  
> hashes (calculated with bitXor) tend towards to a small set of values.  
> This means there are a lot of collisions and each #add: and #includes:  
> is very expensive.
>
>>  How about naming
>>  Collection>>#asPowerset
>>     ^ self asSet powersetInto: (Set new: (2 raisedTo: self size))
>>  with Set>>#powersetInto: and putting that into the next release.
>>
>
> Even now, I'm still not clear on how one takes a change like this and  
> drives it into a squeak release - Tests, Mantis, then what?

Put it on Mantis as enhancement into the collection category. The rest  
follows automatically ;) I suggest to put something like "fast powerset  
method for collections" into the summary line.

> Z.