# [Newbies] Re: Another extension proposal -> subsets

Zulq Alam me at zulq.net
Thu Jul 24 13:13:22 UTC 2008

```Actually, we don't need #permutationsDo: as we're only looking for
combinations. 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

[(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. 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