Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

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

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

    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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2015-07-04 07:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (58 votes), past polls