# returns _2_ closures to generate certain powersets
sub limbic_power_generator {
my $set = shift;
#we start with the original set and count down to the null set
my $set_idx = 2 ** @$set;
#these are the set indexes we should skip
my %skippers = ();
# our first closure generates subsets
my $generator = sub {
#bow out if we're out of sets
return () unless $set_idx;
# Start decrementing the set_idx. We always do this at least once, so
# we get to the next set. Our original number is 2 ** @set, so we start
# at 2 ** @set - 1 after the decrement
while (1) {
$set_idx--;
#boolean to see if we should break out of this loop
my $should_skip = 0;
# here's the slick binary logic. Iterate over each superset we
# should skip. if our current set_idx & (binary and) the skip set is equal
# to the set_idx we're at, then we know that we have a subset of that
# skip set. So we skip this set. $should_skip is set to 1, which means
# we'll stay in our while loop and decrement down to the next set.
foreach my $skip (keys %skippers) {
if (($skip & $set_idx) == $set_idx) {
$should_skip = 1;
last;
}
}
#bow out if this set is NOT a subset of any set we're skipping
last unless $should_skip;
#bow out of the function completely with the null set if we've hit 0.
return () unless $set_idx;
}
# Now we convert our set_idx to binary. Each bit stores whether the element
# is in this subset. For example, set_idx 11 would be 1011, so we keep
# elements 0, 2, and 3.
my @in_set = reverse split //, unpack("B*", pack("N", $set_idx));
# now we return a list. The first element is an arrayref which is the actual
# subset we generated, the second is our set_idx.
# we reverse it to make our lives easier, so don't be surprised when the
# counting gets out of order. Order is irrelevant in this case, anyway.
return ([map { $set->[$_] } grep { $in_set[$_] } (0..$#$set)], $set_idx);
};
# our second closure allows you to add sets to skip
my $skipper = sub { $skippers{$_[0]}++ };
# return both of our closures.
return ($generator, $skipper)
}
#we'll use Limbic~Region's example set.
my $limbic_set = [qw(A B C D)];
#create our iterator and skipper
my ($limbic_iterator, $limbic_skipper) = limbic_power_generator($limbic_set);
#and start cruising over our powersets.
while ( my ($set, $idx) = $limbic_iterator->() ) {
#fancy crap to get it to print out properly.
my $display = {map {$_ => 1} @$set};
printf("%2s%2s%2s%2s (%d)\n", (map {$display->{$_} ? $_ : ' '}
@$limbic_set), $idx);
# now here's the trick, something here will determine a condition whether or
# not this subset matches the search parameters. Let's say, for sake of
# argument, that set_idx 7 (ABC) matches. We'll just set it here.
$limbic_skipper->(7);
# that will prevent sets (AB, AC, A, BC, B, C) from printing out.
}