Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^4: Generating powerset with progressive ordering

by tlm (Prior)
on Apr 26, 2005 at 23:46 UTC ( #451800=note: print w/ replies, xml ) Need Help??


in reply to Re^3: Generating powerset with progressive ordering
in thread 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 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


Comment on Re^4: Generating powerset with progressive ordering
Download Code
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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (12)
As of 2014-12-18 17:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (59 votes), past polls