[Newbies] Re: Another extension proposal -> subsets

cdrick cdrick65 at gmail.com
Fri Jul 25 08:07:26 UTC 2008

```Yes.. Nico's solution is lot faster...

set := #(1 2 3 4 5) asSet.
[ set subsets  "mine"] timeToRun ." 1"
[ set subsets2  "Zulk first"  ] timeToRun. " 8"
[ set subsets4  "Nicolas"] timeToRun. " 1"
[ set subsets5  "Zulk"] timeToRun. " 2"

set := (1 to: 10) asSet.
[ set subsets  ] timeToRun . " 46"
[ set subsets4  ] timeToRun. " 18"
[ set subsets5  ] timeToRun." 114"

set := (1 to: 15) asSet.
[ set subsets  ] timeToRun ." 2484"
[ set subsets4  ] timeToRun. " 1598"
[ set subsets5  ] timeToRun." 12493"

Nicolas won ;) So maybe we can add this one and rename the
combinations:atATime: ?

Cédrick

2008/7/25 Nicolas Cellier <ncellier at ifrance.com>:
> Klaus D. Witzel <klaus.witzel <at> cobss.com> writes:
>
>>
>> On Thu, 24 Jul 2008 20:09:53 +0200, Zulq Alam wrote:
>>
>> 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].
>> >    self do:
>> >      [:each |
>> >      (self copyWithout: each) combinationsInto: aSet].
>> >
>> > 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.
>>
>
> Zulq,
> the algorithm you are proposing is very simple but has major problems:
>
> 1) it is not efficient for large size n: it will do (n factorial) loops when
> only (2 raisedTo: n) are necessary
>        (2 raisedTo: 10) -> 1024
>        (10 factorial) -> 3628800
>
> 2) each loop will result in a costly hash lookup.
> Your hashBlock involve LargeInteger of size (B raisedTo: p) where
> - B is the size of an elementary hash (presumably 4 bytes),
> - p the size of the partition (ranging from 0 to n)
> The cost of a single hash of size p involves p multiplications of growing size.
> Each multiplication of k digits has a cost k^2
> (this is the naive algorithm currently programmed in LargeInteger plugin).
> Thus a single hash costs (B^2+(2*B)^2+...+(p*B)^2)
> Combine this with the (n factorial) loops and you will understand the problem.
>
> 3) the algorithm must store all partitions even if we don't want to collect but
> just to iterate on partitions.
>
> No offense, but you'd better not bother opening a mantis issue for this time.
>
> Cheers
>
> Nicolas
>
>
>
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at lists.squeakfoundation.org
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>
```