[Newbies] Re: Another extension proposal -> subsets

[Nicolas Cellier]

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].
> >    aSet add: 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