Finding the middle permutation
Calculating every permutation is very expensive so you want to avoid doing that. There are some ways to handle this:

1) Sort the characters before you run your algorithm. That way you are sorting a few characters not billions of permutations.

2) If the string has an even number of characters (say abcd) remove the almost middle character (b) and rewrite as something like 'b' + 'acd'.reverse

3) If the string has an odd number of characters (say abcde) you can remove the middle character (c) leaving abde and simplify the result as 'c' + middle_permutation('abcd')

(3) Will always be followed by (2)

So you could rewrite your code as:

def middle_permutation2(string) 
  string = string.chars.sort.join("")
  return string if string.length &lt;= 2

  if string.length.even?
    middle = string.length / 2 - 1
    remainder = string[0...middle] + string[middle+1..-1]
    string[middle] + remainder.reverse

  else
    middle    = string.length / 2
    remainder = string[0...middle-1] + string[middle+1..-1]
    string[middle] + string[middle-1] + remainder.reverse

  end

end