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