Re^2: Generating powerset with progressive ordering

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

Comment on Re^2: Generating powerset with progressive ordering Download Code

Replies are listed 'Best First'.
Re^3: Generating powerset with progressive ordering by Roy Johnson (Monsignor) on Apr 26, 2005 at 20:20 UTC
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]
Re^4: Generating powerset with progressive ordering by tlm (Prior) on Apr 26, 2005 at 23:46 UTC
A powerset should always include the empty set. (The cardinality of the powerset of a set of cardinality n should be 2ⁿ.) 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]
Re^5: Generating powerset with progressive ordering by Roy Johnson (Monsignor) on Apr 27, 2005 at 02:38 UTC
That does simplify it, but it throws off the progressive ordering, which worked out almost magically the way I had it written. For the problem L~R was looking to solve, it was not useful to consider the empty set, either. Probably I should rename the function "non-empty powerset". `:-)` ++ for technical merit. Caution: Contents may have been coded under pressure.	[reply]


good chemistry is complicated, and a little bit messy -LW
	PerlMonks