#!/usr/bin/perl

sub powerset_recurse ($;@) {
    my ( $set, $powerset, $keys, $values, $n, $i ) = @_;

    if ( @_ == 1 ) { # Initialize.
        my $null   = { };
        $powerset  = { $null, $null };
        $keys      = [ keys   %{ $set } ];
        $values    = [ values %{ $set } ];
        $nmembers  = keys %{ $set };    # This many rounds.
        $i         = 0;                 # The current round.
    }

    # Ready?
    return $powerset if $i == $nmembers;

    # Remap.

    my @powerkeys   = keys   %{ $powerset };
    my @powervalues = values %{ $powerset };
    my $powern      = @powerkeys;
    my $j;

    for ( $j = 0; $j < $powern; $j++ ) {
        my %subset = ( );

        # Copy the old set to the subset.
        @subset{keys   %{ $powerset->{ $powerkeys  [ $j ] } }} =
                values %{ $powerset->{ $powervalues[ $j ] } };

        # Add the new member to the subset.
        $subset{$keys->[ $i ]} = $values->[ $i ];

        # Add the new subset to the powerset.
        $powerset->{ \%subset } = \%subset;
    }

    # Recurse.
    powerset_recurse( $set, $powerset, $keys, $values, $nmembers, $i+1 );
}

my $a  = { a => 12, b => 34, c => 56 };
my $pr = powerset_recurse( $a );

print "pr = ", sos_as_string( $pr ), "\n";

# sos_as_string($set) returns a stringified representation of
# a set of sets.  $string is initially undefined, and is filled
# in only when sos_as_string() calls itself later.
#
sub sos_as_string ($;$) {
    my ( $set, $string ) = @_;

    $$string .= '{';                             # The beginning brace

    my $i;                                       # Number of members

    foreach my $key ( keys %{ $set } ) {
        # Add space between the members.
        $$string .= ' ' if $i++;
        if ( ref $set->{ $key } ) {
            sos_as_string( $set->{ $key }, $string );  # Recurse
        } else {
            $$string .= $key;                          # Add a member
        }
    }

    return $$string .= '}';                      # The ending brace
}