powerset operation

Discussion in 'Perl' started by matt, Jan 17, 2004.

  1. matt

    matt Guest

    Hi,

    I would like to know how to implement a powerset operation in perl.
    My friend found the code:

    sub subsets {
    map {
    my $n = $_;
    [@_[grep {$n & 1 << $_} 0..$#_]]
    } (1..2**($#_ + 1));
    }

    online, and that makes sense - but I would like to understand how to
    build a lists of lists etc through the `normal' way of building the
    powerset.

    Normal being akin to the haskell code:
    powerset :: [a] -> [[a]]
    powerset [] = [[]]
    powerset (x:xs) = concat $ [[l, x:l] | l <- powerset xs]

    my closest perl approximation is:

    sub subsets {
    my @list;
    @list = @_;

    return (()) if ($#list < 0);

    my @subs;
    @subs = subsets(@subs[1..$#subs]);

    my @with;
    @with = @subs;
    foreach (@with) {
    push(@{$_}, $list[0]);
    push(@subs, [ $_ ]);
    }

    return @subs;
    }


    but this doesn't seem to work. (I'm relatively new to perl, but am a
    somewhat well-versed unix and ruby user, if where I'm coming from
    matters in explanations...)
    matt, Jan 17, 2004
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim Rowe

    Powerset

    Tim Rowe, Sep 15, 2003, in forum: Python
    Replies:
    0
    Views:
    531
    Tim Rowe
    Sep 15, 2003
  2. Gunnar G

    powerset

    Gunnar G, Aug 9, 2005, in forum: C++
    Replies:
    1
    Views:
    515
    Karl Heinz Buchegger
    Aug 9, 2005
  3. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    6
    Views:
    991
    Carsten Haese
    Jul 13, 2007
  4. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    0
    Views:
    421
    Evan Klitzke
    Jul 13, 2007
  5. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    1
    Views:
    386
    Mark Dickinson
    Jul 14, 2007
Loading...

Share This Page