Re^4: Generating powerset with progressive ordering

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

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

Replies are listed 'Best First'.
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]