Re: Powerset short-circuit optimization

[tilly]

Sorry for taking so long to do this. I saw how to do it fairly quickly but didn't get time to write it up.

Fun problem. Figuring out how my solution works is also fun. ;-)

Incidentally the fact that you didn't want the empty set made life easier - I could just use the empty set as my "end of data" metadata marker. If I didn't have that, then I'd have had to use a less convenient API. (I'd have probably just returned array references instead.)

Note that I suspect a naive approach such as the ones above is actually faster.

#! /usr/bin/perl -w
use strict;

my $iterator = Set::IterateAndSkip->new(
  @ARGV ? @ARGV : 'A'..'D'
);

while (my @subset = $iterator->next) {
  print @subset, ":\tskip? ";
  if (<STDIN> =~ /y/i) {
    $iterator->skip_subsets;
  }
}
print "Done\n";

package Set::IterateAndSkip;

sub new {
  my $class = shift;
  my $set = [map {[1, $_]} @_];
  $set->[0][0] = 0;
  return bless {
    set => $set,
  }, $class;
}

sub end_of_first_run {
  my $self = shift;
  my $set = $self->{set};
  my $n = -1;
  for (@$set) {
    if ($_->[0]) {
      $n++;
    }
    else {
      last;
    }
  }
  return $n;
}

sub skip_subsets {
  my $self = shift;
  $self->{set}[0][0] = 0;
}

sub next {
  my $self = shift;
  my $set = $self->{set};
  my $end = $self->end_of_first_run;

  if (-1 < $end) {
    $set->[$end][0] = 0;
  }
  else {
    $set->[0][0] = 1;
    $end = $self->end_of_first_run;
    if ($end == $#$set) {
      if ($self->{started}) {
        # Reinitialize in case we want to cycle through again.
        delete $self->{started};
        $set->[0][0] = -1;
        return ();
      }
      else {
        $self->{started} = 1;
      }
    }
    else {
      $set->[$end][0] = 0;
      $set->[$end + 1][0] = 1;
    }
  }
  my @result = map {$_->[0] ? $_->[1] : ()} @$set;
  # Need to skip the empty set.
  return @result ? @result : $self->next();
}