Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

Re^2: Generating powerset with progressive ordering

by Limbic~Region (Chancellor)
on Feb 25, 2005 at 20:46 UTC ( #434636=note: print w/replies, xml ) Need Help??

in reply to Re: Generating powerset with progressive ordering
in thread Generating powerset with progressive ordering

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 }->() }; }
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

Replies are listed 'Best First'.
Re^3: Generating powerset with progressive ordering
by Roy Johnson (Monsignor) on Apr 26, 2005 at 20:20 UTC
    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.

    Caution: Contents may have been coded under pressure.

      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 ); }
      I imagine that this means that only two states are needed in iter_powerset.

      the lowliest monk

        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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://434636]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2020-10-27 12:11 GMT
Find Nodes?
    Voting Booth?
    My favourite web site is:

    Results (256 votes). Check out past polls.