For set A B C, you can enumerate the powerset in binary:
111 ABC
110 AB
101 A C
100 A
011 BC
010 B
001 C
000
For BCD, it would be thus:
111 BCD
110 BC
101 B C
100 B
011 CD
010 C
001 D
000
Instead, we want to offset the values in BCD and leave an empty slot for A. We'll end up with this:
0111 BCD
0110 BC
0101 B C
0100 B
0011 CD
0010 C
0001 D
0000
####
(for ABC)
Have we seen A before? No? A = slot 0
Have we seen B before? No? B = slot 1
Have we seen C before? No? C = slot 2
(for BCD)
Have we seen B before? YES - return 1
Have we seen C before? YES - return 2
Have we seen D before? No? D == slot 3
####
By using a dead bit for A, we actually have this:
1111 invalid
1110 invalid
1101 invalid
1100 invalid
1011 invalid
1010 invalid
1001 invalid
1000 invalid
0111 BCD
0110 BC
0101 B C
0100 B
0011 CD
0010 C
0001 D
0000
####
11111111111111111111111111 invalid
11111111111111111111111110 invalid
11111111111111111111111101 invalid
.
.
.
00000000000000000000000010 invalid
00000000000000000000000001 valid (z)
####
From up above, set (z)
start at 11111111111111111111111111
deadbit string = 11111111111111111111111110
start & deadbit = 11111111111111111111111110
this is > 0, so xor.
(start ^ deadbit) & start = 00000000000000000000000001
Bang! one and, a conditional, and an xor jumped you past 67 million some odd invalid sets.
Another one, from above, set (ABCD)
start at 1111
deadbit string = 1110
start & deadbit = 1110
this is > 0, so xor
(start ^ deadbit) & start = 0111 (starts at BCD
Here's a more complex example. Assume our first set was ABC, and our next was ABD. (A = 0, B = 1, C = 2, D = 3). When we hit ABD, we flag C as our deadbit and our deadbit string would be 0010.
Let's try a complete runthrough:
1111
1111 & 0010 > 0 -> (1111 ^ 0010) & 1111 -> new index is 1101
1101 ABD (1101 & 0010 == 0)
1100 AB (1100 & 0010 == 0)
1011 (1011 & 0010 == 0)
1011 & 0010 > 0 -> (1011 ^ 0010) & 1011 -> new index is 1001
1001 A D (1001 & 0010 == 0)
1000 A (1000 & 0010 == 0)
0111
0111 & 0010 > 0 -> (0111 ^ 0010) & 0111 -> new index is 0101
0101 B D (0101 & 0010 == 0)
0100 B (0100 & 0010 == 0)
0011
0011 & 0010 > 0 -> (0011 ^ 0010) & 0010 -> new index is 0001
0001 D (0001 & 0010 == 0)
0000 () (0000 & 0010 == 0)
####
use strict;
use warnings; # returns _3_ closures to generate certain powersets
#arbitrary benchmark device, used to se how many times the iterator was called.
my $calls = 0;
sub limbic_power_generator {
my $set = shift;
# we re-define skippers as an array and allow the user to pass it in, so we
# can keep track of previously skipped values. The value of the hash was
# that it prevents dupes. Note - it would be better to mod the old version
# to always use a descendingly sorted array, but is left to the reader.
my $skippers = shift || {};
my $deadbits = shift || 0;
#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 {
# arbitrary benchmark device, that way you can see how may times the iterator
# was called
$calls++;
#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--;
# check to see if this set contains a deadbit, and if so hop over it.
if ($set_idx & $deadbits) {
# make sure that we don't accidentally jump up to a higher set index.
# this can happen if you have deadbits beyond the length of your set
$set_idx = ($set_idx ^ $deadbits) & $set_idx;
}
#bow out if this set is NOT a subset of any set we're skipping
last unless $skippers->{$set_idx};
#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 = split //, unpack("b*", pack("V",$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.
return ([map { $set->[$_] } grep { $in_set[$_] } (0..$#$set)], $set_idx);
};
# our second closure allows you to add sets to skip
# it also returns the list of skipped values
my $skipper = sub {
if (@_) {
my $skip_key = shift;
$skippers->{$skip_key}++;
}
return $skippers;
};
# return both of our closures.
return ($generator, $skipper)
}
# we'll use the example sets from node 580625
my $limbic_sets = [
[qw(A B C)],
[qw(A B D)],
[qw(A B)],
[qw(B C)],
[qw(E)],
[qw(A B C E)],
[qw(A B C D E)],
];
# our index lookup hash. There are potential savings by pre-caching these values
# if all elements are known in advance.
my %idx = ();
my $next_open_idx = 0;
# our sets to skip
my %skippers = ();
foreach my $limbic_set (@$limbic_sets) {
print "checks set @$limbic_set\n";
# we need to keep track of which indexes are dead, so we copy the
# known indexes
my %dead_idx = %idx;
# here we'll keep track of the bits that are dead
my $deadbits = 0;
# we now need to iterate over our set. If we know the index of that element
# then great. That means we've seen it before, and it's currently live, so
# delete it from our list of dead bits.
#
# otherwise, assign it a new index.
foreach my $elem (@$limbic_set) {
if (defined $idx{$elem}) {
delete $dead_idx{$elem};
}
else {
$idx{$elem} = $next_open_idx++;
}
}
#here we're going to store the indexes which are dead
my %dead_lookup = ();
# iterate over our dead elements list, and toss it into the deadbits string
# and add its index to the lookup
foreach my $idx (values %dead_idx) {
$deadbits |= 2 ** $idx;
$dead_lookup{$idx}++;
}
# we need to pad out set with dead bits. So if we call with (ABC), then later
# with (ABD), we need to turn that into (AB D)
my $padded_limbic_set = [];
my $padded_limbic_idx = 0;
foreach my $idx (0..$#$limbic_set) {
# if that index is dead, then toss in a placeholder and shift the array
# element forward. This is using parallel indexes, there may be a more
# efficient method.
if ($dead_lookup{$padded_limbic_idx}) {
$padded_limbic_set->[$padded_limbic_idx++] = undef;
redo;
}
$padded_limbic_set->[$padded_limbic_idx++] = $limbic_set->[$idx];
}
# get our iterators, using the padded set, skippers, and deadbits.
my ($limbic_iterator, $limbic_skipper) = limbic_power_generator($padded_limbic_set, \%skippers, $deadbits);
#as we see an eleemnt, we're going to add it to this list, so we skip it on the next pass.
my %future_skippers = ();
#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} grep {defined} @$set};
my $format = "%2s" x scalar(@$padded_limbic_set) . " (%d)\n";
printf($format, (map {defined $_ && $display->{$_} ? $_ : ' '} @$padded_limbic_set), $idx);
#we don't skip anything in this pass, but we'll do it the next time around.
$future_skippers{$idx}++;
}
@skippers{keys %future_skippers} = values %future_skippers;
}
print "TOTAL CALLS $calls\n";
####
#!/usr/bin/perl
use strict;
use warnings;
sub set_generator {
my ($set, $set_idx, $skippers, $deadbits) = @_;
# 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 ($set_idx--) {
# check to see if this set contains a deadbit, and if so hop over it.
# make sure that we don't accidentally jump up to a higher set index.
# this can happen if you have deadbits beyond the length of your set
$set_idx = ($set_idx ^ $deadbits) & $set_idx;
#bow out if this set is NOT a subset of any set we're skipping
last unless $skippers->{$set_idx};
#bow out of the function completely with the null set if we've hit 0.
}
#bow out if we're out of sets
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 = split //, unpack("b*", pack("L",$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.
return ([map { $set->[$_] } grep { $in_set[$_] } (0..$#$set)], $set_idx);
};
# our index lookup hash. Assume letters 'a'-'z'. The original version of
# dynamically assigning indexes had a few bugs. Whoops. So now you're required
# to know all elements in advance. Damn. I'll fix this later, I guess.
my @letters = ('a'..'z');
my %idx = map {$letters[$_] => $_} (0..25);
# our sets to skip
my %skippers = ();
while (my $limbic_string = <>) {
chomp $limbic_string;
my $limbic_set = [split //, $limbic_string];
# we need to keep track of which indexes are dead, so we copy the
# known indexes
my %dead_idx = %idx;
# here we'll keep track of the bits that are dead
my $deadbits = 0;
#remove the live bits from the dead set.
delete @dead_idx{@$limbic_set};
# iterate over our dead elements list, and toss it into the deadbits string
# and splice in an undef to our list.
foreach my $idx (sort {$a <=> $b} values %dead_idx) {
$deadbits |= 2 ** $idx;
splice @$limbic_set, $idx, 0, undef unless $idx >= @$limbic_set;
}
#as we see an element, we're going to add it to this list, so we skip it on the next pass.
my @future_skippers = ();
my $set_idx = 2 ** @$limbic_set;
#and start cruising over our powersets.
while (my ($set, $newidx) = set_generator($limbic_set, $set_idx, \%skippers, $deadbits)) {
print @$set,"\n";
#note our new set index
$set_idx = $newidx;
#we don't skip anything in this pass, but we'll do it the next time around.
push @future_skippers, $set_idx;
}
@skippers{@future_skippers} = (1) x @future_skippers;
}