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(&: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
• You might be interested in this question: codereview.stackexchange.com/q/62194/31562 . Even though I did it for combinations, it's possible to adapt it to work for permutations. – Simon Forsberg May 14 '17 at 0:01
• It's inefficient to actually make all the permutations. Can you count how many permutations start with a given letter without enumerating them? Now can you figure out which letter the middle permutation starts with? (Etcetera.) – aes May 14 '17 at 7:37
• It's always a good idea to get some rough guesstimates about the problem sizes involved before setting out on a solution. For your solution, for example, let's look at what happens with a string with, say, 15 characters. That's 1307674368000 (1.3 trillion) permutations. Even if you had a 5GHz CPU and even if it took only 1 clock cycle to generate one permutation, it would already take more than 4 minutes. And the array of permutations needs about 18TB of RAM. Sorting an array is O(n log n) comparisons (where n is the number of elements). Comparing two strings is O(n) (where n is the number of – Jörg W Mittag May 15 '17 at 8:07
• … characters, so the sort is about O(n*n! log n!) in the length of the string, a function which looks like this. – Jörg W Mittag May 15 '17 at 8:16

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 <= 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