# 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. } ##```## ABCD| ABC |ABC | AB D| |AB D AB |AB |AB A CD| | |A CD A C |A C | |A C A D| |A D| A |A |A |A BCD| | | | BCD BC | BC | | | BC B D| | B D| | B D B | B | B | | B CD| | | CD| CD C | C | | C | C D| | D| D| D () ```