[Newbies] Re: Another extension proposal -> subsets

Zulq Alam me at zulq.net
Fri Jul 25 08:55:01 UTC 2008

Nicolas Cellier wrote:

> 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

It's better than N! because it will not loop over a set already 
processed. For instance, for a set of 5 elements it will try 81 sets but 
only process 32 of these. Not 120 in either case (5 factorial).

> 2) each loop will result in a costly hash lookup.
> Your hashBlock involve LargeInteger of size (B raisedTo: p) where

It doesn't need to. That was just a very rough attempt at producing a 
hash that didn't evaluate to only 16 values. It should be possible to 
create one that produces SmallIntegers but with a higher cardinality.

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

Agreed. I was just curious about why the naive algorithm was so slow and 
then as a seperate question how one gets such changes in.


More information about the Beginners mailing list