#!/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;
}