Try this. It's a re-casting of the Python algorithm to operate on arrays:

#! perl -slw
use strict;

sub permute3 {
    my( $in, $pre ) = ( @_, [] );
    return print join '-', @$pre unless @$in;
    permute3(
        [ @{ $in }[ 0 .. $_-1, $_+1 .. $#$in ] ],
        [ @$pre, $in->[ $_ ] ]
    ) for 0 .. $#$in;
}

permute3( [ qw[ apple banana orange ] ] );;
__END__
C:\test>junk36
apple-banana-orange
apple-orange-banana
banana-apple-orange
banana-orange-apple
orange-apple-banana
orange-banana-apple
[download]