[Newbies] Re: Another extension proposal -> subsets

Klaus D. Witzel klaus.witzel at cobss.com
Thu Jul 24 15:54:09 UTC 2008


On Thu, 24 Jul 2008 15:13:22 +0200, Zulq Alam wrote:

> Actually, we don't need #permutationsDo: as we're only looking for  
> combinations.

Permutations? (n factorial)? v.s. (2 raisedTo: n)?

> With a few optimisations:
>
> combinations
>    ^ self combinationsInto: (Set new: (2 raisedTo: self size))
>
> combinationsInto: aSet
>    (aSet includes: self) ifTrue: [^ self]. "optimisation"
>    aSet add: self.
>    self do:
>      [:each |
>      (self copyWithout: each) combinationsInto: aSet].	
>    ^ aSet

Yeah, that's a good one :)

> [(1 to: 8) asSet combinations] timeToRun "215"
> [(1 to: 9) asSet combinations] timeToRun "918"
> [(1 to: 10) asSet combinations] timeToRun "3989"
> [(1 to: 11) asSet combinations] timeToRun "16349" 	
> [(1 to: 12) asSet combinations] timeToRun  "68780"
>
> So a little better, but I was expecting much more.

I think that the amount of work for (n + 1) is about (timeToRun of: n) *  
3; should be observable better with larger n's ;)

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.

How about naming

Collection>>#asPowerset
	^ self asSet powersetInto: (Set new: (2 raisedTo: self size))

with Set>>#powersetInto: and putting that into the next release.

/Klaus

> What's worrying is this:
>
> (1 to: 10) asSet combinations size  "1024"
> ((1 to: 10) asSet combinations collect: [:e | e hash]) asSet size "16"
>
> So, 1024 distinct Sets have only 16 distinct hashes between them? That  
> seems pretty bad. It would probably be possible to get a little bit more  
> out of the routine with a better (more appropriate) hash function. Even  
> so, I don't think it will ever be as fast as your method but will  
> happily be proved wrong! :)
>
> Z.
>
> cdrick wrote:
>>> Set>>subsets
>>>  | subsets |
>>>  subsets := Set with: self.
>>>  self asArray permutationsDo: [:e | subsets add: e asSet].
>>>  self do: [:e | subsets addAll: (self copyWithout: e) subsets].
>>>  ^ subsets
>>  nice too and frustrating how you got it quick :)
>>  I tried a recursive method too first but found the byte ressemblance  
>> so...
>> My only consolation is that the recursive solution (subsets2) is
>> slower and hardly work for Set with more than 10 elements.
>>  set := #(1 2 3 4 5) asSet.
>> [ set subsets  ] timeToRun ." 1"
>> [ set subsets2  ] timeToRun. " 8"
>>  set := #(1 2 3 4 5 6 7) asSet.
>> [ set subsets  ] timeToRun ." 5"
>> [ set subsets2  ] timeToRun. " 233"
>>  set := #(1 2 3 4 5 6 7 8 ) asSet.
>> [ set subsets  ] timeToRun . " 11"
>> [ set subsets2  ] timeToRun. " 1683"
>>  set := (1 to: 10) asSet.
>> [ set subsets  ] timeToRun . " 46"
>>  set := (1 to: 15) asSet.
>> [ set subsets  ] timeToRun ." 2484"
>>  set := (1 to: 20) asSet.
>> [ set subsets  ] timeToRun .  "559953"  "but here the result has (2
>> raisedTo: 20)  1 048 576 Sets :)"
>>  set := (1 to: 50) asSet.
>> [ set subsets  ] timeToRun .    "I got a "space is low   wow" :)
>>  I have to go,
>> That was fun :)
>>  See you
>>  Cédrick
>>    
>> ------------------------------------------------------------------------
>>  _______________________________________________
>> Beginners mailing list
>> Beginners at lists.squeakfoundation.org
>> http://lists.squeakfoundation.org/mailman/listinfo/beginners




More information about the Beginners mailing list