You can also go the inefficient but straightforward way, just everywhere use an iterator, and compose iterators to get new iterators. And, of course, iterators can be built out of closures. Try the following:

sub ret_permute_iter {
  if (@_ < 2) {
    my @vals = ("garbage", @_);
    return sub {
      shift @vals;
      return @vals;
    };
  }
  else {
    my ($cur, @left) = @_;
    my @done;
    my $iter = ret_permute_iter(@left);
    return sub {
      my @res = $iter->();
      if (@res) {
        return ($cur, @res);
      }
      elsif (@left) {
        push @done, $cur;
        $cur = shift @left;
        $iter = ret_permute_iter(@done, @left);
        @res = $iter->();
        return ($cur, @res);
      }
      else {
        return;
      }
    };
  }
}

my $demo_iterator = ret_permute_iter(1..5);
foreach (1..120) {
  print $demo_iterator->(), "\n";
}
[download]

I won't compare speed to tye's because, um, I am much slower. :-) But you can arrive at this iterator approach from the standard list-based approach in a fairly mechanical fashion, and it is worthwhile figuring out how I did that.