Finding the middle permutation This method finds all permutations of a string and stores them in a sorted array. It then returns the element in the middle of the array. 

def middle_permutation(string)
  sorted = string.chars.to_a.permutation.map(&amp;:join).sort
  sorted[sorted.length / 2 - 1]
end


For strings over 10+ characters this code is too slow. How can I speed it up?

Here are my tests. They pass, but I'd like it to be more efficient:

describe "Basic tests" do
  Test.assert_equals(middle_permutation("abc"),"bac")
  Test.assert_equals(middle_permutation("abcd"),"bdca")
  Test.assert_equals(middle_permutation("abcdx"),"cbxda")
  Test.assert_equals(middle_permutation("abcdxg"),"cxgdba")
  Test.assert_equals(middle_permutation("abcdxgz"),"dczxgba")
end
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