powerset operation

From: matt (mhm26_at_drexel.edu)
Date: 01/17/04

  • Next message: Erik Tank: "Re: multiple row updates in MYSQL using HTML"
    Date: 16 Jan 2004 22:50:38 -0800
    
    

    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...)


  • Next message: Erik Tank: "Re: multiple row updates in MYSQL using HTML"