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@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners