3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Simon Forsberg May 14 '17 at 0:01
  • \$\begingroup\$ 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.) \$\endgroup\$ – aes May 14 '17 at 7:37
  • \$\begingroup\$ 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 \$\endgroup\$ – Jörg W Mittag May 15 '17 at 8:07
  • \$\begingroup\$ … characters, so the sort is about O(n*n! log n!) in the length of the string, a function which looks like this. \$\endgroup\$ – Jörg W Mittag May 15 '17 at 8:16
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.