in reply to Generating powerset with progressive ordering

I had an easier time thinking of this as manipulating the characteristic sequence of the subsets (i.e, a string of 0's and 1's, where the first bit is a 1 if the first factor is included in the subset, etc). If you look at the characteristic sequences given in your example, you can see that there are three rules being applied (you can print out $str to see what's going on under the covers). Anyway, this code does its manipulations on the characteristic sequence and converts it to the appropriate subset: 
sub iter {
    my @factors = @_;
    my $str;

    return sub {
        if (not defined $str) {
            $str =  "1" . ("0" x $#factors);
            return map { substr($str, $_, 1) ? $factors[$_] : () }
                   0 .. $#factors;
        }
        for ($str) {
            s/0(0*)$/1$1/
              or s/11$/01/
              or s/^(.*)10(.*)$/"${1}01" . "0" x length $2/e
              or return;
        }

        return map { substr($str, $_, 1) ? $factors[$_] : () }
               0 .. $#factors;
    };
}   

my $i = iter( 2, 3, 5, 7 );
while (my @s = $i->()) {
    print "@s\n";
}

__END__
2
2 3
2 3 5
2 3 5 7
2 3 7
2 5
2 5 7
2 7
3
3 5
3 5 7
3 7
5
5 7
7

[download]
I'd be interested to see this simplified a bit. I know you mentioned in the CB that tye had an idea for a solution, and I wonder if he's able to implement it with manipulations to the subsets themselves instead of their characteristic sequences.

You also mentioned wanting to know when the "next phase" of iterations began (the horizontal lines in your example). You can figure this out by checking which substitution rule was actually applied.

Update: Here is the code with the "next phase" markers: 

sub iter {
    my @factors = @_;
    my $str;
    my $break = 0;

    return sub {
        if (not defined $str) {
            $str =  "1" . ("0" x $#factors);
            return map { substr($str, $_, 1) ? $factors[$_] : () }
                   0 .. $#factors;
        }
        for ($str) {
            s/0(0*)$/1$1/ and last;

            return "BREAK" if $break = !$break;


            s/11$/01/
              or s/^(.*)10(.*)$/"${1}01" . "0" x length $2/e
              or return;
        }

        return map { substr($str, $_, 1) ? $factors[$_] : () }
               0 .. $#factors;
    };
}


my $i = iter( 2, 3, 5, 7 );

while (my @s = $i->()) {
    print "@s\n";
}

__END__
2
2 3
2 3 5
2 3 5 7
BREAK
2 3 7
BREAK
2 5
2 5 7
BREAK
2 7
BREAK
3
3 5
3 5 7
BREAK
3 7
BREAK
5
5 7
BREAK
7
BREAK

[download]

blokhead

Replies are listed 'Best First'.
Re^2: Generating powerset with progressive ordering
by fizbin (Chaplain) on Feb 25, 2005 at 19:43 UTC
    Huh - so apparently your method and my evil method ended up being the same, or at least very similar. Note that you can improve this slightly by consolidating your last two expressions and eliminating the need for an "e" flag on the substitutions: 
       for ($str) {
     s/0(0*)$/1$1/
     or s/1(0*)1$/01$1/
     or return;
   }

    [download]
    And actually, we can combine your method and the last bit in my post to get this somewhat natural structure for looping through the possibilities: 
    sub nextmask {
     if ($_[0] =~ s/0(0*)$/1$1/) {1;}
     elsif ($_[0] =~ s/1(0*)1$/01$1/) {2;}
     else {0;}
}

my @factors = qw(2 3 5 7);
my $mask = '0' x scalar(@factors);
while (my $transtype = nextmask($mask))
{

  print "BREAK\n" if ($transtype > 1);
  # do stuff 
  print join " ", 
        map { substr($mask, $_, 1) ? $factors[$_] : ' ' }
                     0 .. $#factors;
  print "\n";
}

    [download]
    (I've never liked do { ... } while() loops) 
    --
@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/;
map{y/X_/\n /;print}map{pop@$_}@/for@/

    [download]
[reply]
[d/l]
[select]
Re^2: Generating powerset with progressive ordering
by Limbic~Region (Chancellor) on Feb 25, 2005 at 20:46 UTC
    blokhead,
    I doubt this is how tye would have implemented it, but this is 1 implementation of his 3 simple rules: 
    #!/usr/bin/perl
use strict;
use warnings;

my $next = iter_powerset( 1,2,3,4,5 );
while ( my @combo = $next->() ) {
    print "@combo\n";
}

sub iter_powerset {
    my @factor = @_;
    my $end = $#factor;
    my @subset = (undef) x $end;
    my ($pos, $mode) = (-1, 1);
    my $return = sub { return @factor[ grep defined, @subset ] };
    my %dispatch = (
        1 => sub {
            ++$pos;
            $subset[ $pos ] = $pos;
            ++$mode if $pos == $end;
            $return->();
        },
        2 => sub {
            $subset[ $pos - 1 ] = undef;
            ++$mode;
            $return->();
        },
        3 => sub {
            $subset[ $pos-- ] = undef;
            while ( $pos >= 0 ) {
                last if defined $subset[ $pos ];
                --$pos;
            }
            $subset[ $pos++ ] = undef;
            return () if ! $pos;
            $subset[ $pos ] = $pos;
            $mode = 1;
            $return->();
        },
    );
    return sub { $dispatch{ $mode }->() };
}

    [download]
    I am now going to play with making it closer to what I want for the other task.

    Cheers - L~R

    Since tye's 3 simple rules were uttered in passing on the CB, I will summarize them here to help explain the code
    • Mode 1: Fill to the right until you reach the end
    • Mode 2: Remove second to last element
    • Mode 3: Remove last element, increment new last element
[reply]
[d/l]
      Limbic,
      In hopes of better understanding what you were doing, I implemented powersets first as a recursive function and then as an iterator that tries to parallel the recursive version. I thought you might be interested to see what I came up with.
      Read more... (2 kB)
      Caution: Contents may have been coded under pressure.
[reply]
[d/l]
[select]

        A powerset should always include the empty set. (The cardinality of the powerset of a set of cardinality n should be 2n.) Therefore, you can simplify powerset: 

        sub powerset {
  my ( $car, @cdr ) = @_;
  my @cdr_powerset = @cdr ? powerset( @cdr ) : [];
  return ( @cdr_powerset, map [ $car, @$_ ], @cdr_powerset );
}

        [download]
        I imagine that this means that only two states are needed in iter_powerset.

        the lowliest monk

[reply]
[d/l]

In Section Seekers of Perl Wisdom