Re: Glob powerset with progressive ordering

This is insanely clever! ++

Though I agree with using the term "iterator" for this snippet, it is worth noting that the space requirement grows at least¹ as ~ log(N)(2N-1)², so it is not an "iterative algorithm" (whose space requirements would be constant).

¹I write "at least" because I haven't the foggiest idea of what perl is doing under the hood with glob; for all I know, it pre-computes all 2^N -1 elements and dishes them out one by one.

Update: Added a missing log factor to my estimate for the space requirement; it arises from the fact that the number of digits per element grows logarithmically with N.

the lowliest monk

Comment on Re: Glob powerset with progressive ordering

Replies are listed 'Best First'.
Re^2: Glob powerset with progressive ordering by Roy Johnson (Monsignor) on Apr 27, 2005 at 10:53 UTC
Please note that there are two examples in the snippet. The first doesn't have the explosive-growth problem (though it does still have the log factor). It looks like glob does precompute all elements and then dish them out one by one. You can see this by trying `my $iter = iter_powerset(1..20);`. The wait is a dead giveaway. So to get a real iterator, you have to write your own.How disappointing. Caution: Contents may have been coded under pressure.	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: Glob powerset with progressive ordering
by Roy Johnson (Monsignor) on Apr 27, 2005 at 10:53 UTC

It looks like glob does precompute all elements and then dish them out one by one. You can see this by trying my $iter = iter_powerset(1..20);. The wait is a dead giveaway. So to get a real iterator, you have to write your own.How disappointing.

Caution: Contents may have been coded under pressure.

[reply]
[d/l]