My basic idea is to map the array indices to bits in a binary number. If a bit is on, you take that element out of the source array. For example:
0 = 0b0000 --> {nothing}
3 = 0b0011 --> 'horse:cow'
13 = 0b1101 --> 'horse:dog:cat'
The algorithm then simply becomes a loop over 1 .. 2**@kw -1, testing the bits for each number.
Here's my first implementation of it. It's probably not as efficient as possible yet.
sub rhesa {
# initial source in sequence order
my $source = 'horse:cow:dog:cat';
my @kw = split /:/, $source;
my @res;
for my $i( 1 .. 2**@kw - 1 ) {
my @ar; my $t;
while( $i > 0 ) {
push @ar, $kw[$t] if $i & 1;
$i >>= 1; $t++;
}
push @res, join ':', @ar;
}
return @res;
}
I'm a bit irritated with the number of temporary variables, but I can't think of anything prettier just now. Hope it helps :)
BTW, a simple Benchmark comparison showed a 200% speed increase over your version.