You're handling the input as an array, which is fine, but if you take a string of characters instead it can be useful to know that there is a neat trick to check whether $derange is a derangement of $string:

  if (($derange ^ $string) !~ /\0/) {
    print "'$derange' is a derangement\n";
  }
[download]

I suspect there is a way to solve the complete problem for strings using a single s/// substitution to generate the "next" permutation (starting with a Unicodabetically-sorted string), but I don't see an easy way to do it off the top of my head - you need to replace the character preceding the longest reverse-sorted trailing substring with the next available character and sort what's left, which sounds likely to involve some fairly ugly (??{...}) code.