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]

Here's a version that uses a separate array to mark when a item is used instead of building and destroying anon arrays.

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1186402

use strict;
use warnings;

my @items = qw( apple banana orange );
my @used;

sub permute
  {
  @_ == @items and return print "@_\n";
  $used[$_]++ || permute(@_, $items[$_]), $used[$_]-- for 0 .. $#items
+;
  }

permute();
[download]