Here's my somewhat golfed variation:

sub rhesa2 {
    my $source = shift;
    my @kw = split /:/, $source;
    map {
        my (@ar, $t);
        do {
            ($_ & 1) and push @ar, $kw[$t];
                $t++;
        } while ($_ >>= 1);
        join ':', @ar
    } ( 1 .. 2**@kw - 1 )
}

my @res = rhesa2('horse:cow:dog:cat');
[download]