#!/usr/bin/perl

# The mask cache for the powerset_iter().
my @_powerset_iterate_mask = ( );

sub powerset_iterate {
    my $set = shift;

    my @keys     = keys   %{ $set };
    my @values   = values %{ $set };
    # The number of members in the original set.
    my $nmembers = @keys;
    # The number of subsets in the powerset.
    my $nsubsets = 1 << $nmembers;
    my ( $i, $j, $powerset, $subset );

    # Compute and cache the needed masks.
    if ( $nmembers > @_powerset_iterate_mask ) {
        for ( $j = @_powerset_iterate_mask; $j < $nmembers; $j++ ) {
            # The 1 << $j works reliably only up to $nmembers == 31.
            push( @_powerset_iterate_mask, 1 << $j );
        }
    }

    for ( $i = 0; $i < $nsubsets; $i++ ) {
        $subset = { };
        for ( $j = 0; $j < $nmembers; $j++ ) {
            # Add the ith member if it is in the jth mask.
            $subset->{ $keys[ $j ] } = $values[ $j ]
                if $i & $_powerset_iterate_mask[ $j ];
        }
        $powerset->{ $subset } = $subset;
    }

    return $powerset;
}

my $a  = { a => 12, b => 34, c => 56 };

my $pi = powerset_iterate( $a );

print "pi = ", sos_as_string( $pi ), "\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
}