Glob powerset with progressive ordering

Dedicated to my comrade-in-obsessing, Limbic~Region (whom I invite to translate this into Perl6).
A seldom-used feature of glob is that it acts as an iterator when in scalar context. Here's how to use it as the workhorse for generating a powerset iteratively. To avoid any special characters showing up in the glob string, the actual values are put in an array, and the indices are used in the glob string. The "+" char is used as a separator. To extract the elements, the string returned from glob is split on + and used to index the array.

Using this technique, the task of creating an iterator boils down to creating a glob string.

# This one constructs a simple glob and returns the sub that will
# iterate through it.
sub iter_powerset {
  my @elems = @_;
  my $glob_str = join 'X', map {"{$_,}"} 0..$#elems;
  sub { @elems[grep length, split 'X', scalar glob $glob_str] };
}

# This is an auxiliary to iter_powerset2 (below). The glob expression 
+is
# more complex, in order to get the desired order of output. As the nu
+mber
# of elements grows, the glob string balloons, quickly becoming too la
+rge
# to work.
sub powerset_glob {
  my ($car, @cdr) = @_;
  if (@cdr) {
    my $cdr_globstr = powerset_glob(@cdr);
    return (join ',', "{$car", "$car+$cdr_globstr", "$cdr_globstr}");
  }
  else { return $car }
}

# Call the glob string builder and return the iterator subroutine
sub iter_powerset2 {
  my @elems = @_;
  my $glob_str = powerset_glob(0..$#elems);
  sub { @elems[grep length, split /\+/, scalar glob $glob_str] };
}

# Demonstration code. Call either iter_powerset function
my $iter = iter_powerset2(2,3,5,7);
while (my @set = $iter->()) {
   print "<@set>\n";
}
[download]

Comment on Glob powerset with progressive ordering Download Code

Replies are listed 'Best First'.
Re: Glob powerset with progressive ordering by tlm (Prior) on Apr 27, 2005 at 07:10 UTC
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	[reply]
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]