use strict;
use warnings;

# initial source in sequence order
my $source = 'horse:cow:dog:cat';

# hash used to store results (weed out dups)
my %hash;

function(\%hash, $source);

# and now the results
foreach (keys %hash) {
    print "$_\n";
}

# generate array of combinations
# (hash keys are the results)
sub function {
    my $hash_ref = shift;
    my $source = shift;

    # skip it if we've been here
    return if $hash_ref->{$source};

    $hash_ref->{$source}++;

    # remove one of each part from the whole
    if ((my @parts = split(/:/, $source)) > 1) {
        for (my $i = 0; $i < @parts; $i++) {
            my @parts_copy = split(/:/, $source);
            splice(@parts_copy, $i, 1);
            function($hash_ref, join(':',@parts_copy));
        }
    }
    return;
}
[download]