Simple Fun #159: Middle Permutation

Question

Task

You are given a string s. Every letter in s appears once.

Consider all strings formed by rearranging the letters in s. After ordering these strings in dictionary order, return the middle term. (If the sequence has a even length n, define its middle term to be the (n/2)th term.)

The problem

Hey guys. I am totaly stuck... I`ve got an algorithm to calculate the answer in O(n). All basic tests are passed. But I constantly fail all tests, where the lenght of string equals 23,24,25. Some scary stuff happens, always like this:

'noabcdefgijklymzustvpxwrq' should equal 'nmzyxwvutsrqpolkjigfedcba'

'lzyxvutsrqonmeijhkcafdgb' should equal 'lzyxvutsrqonmkjihgfedcba'

I mean that it goes in the right direction, but suddenly mistakes. Give me a hint what I should check or what thing to fix. Thanks a lot!

P.S. This execute middlePermutation in under 12000ms gave me the idea of solving

Code

import math

def middle_permutation(string):
    ans, tmp = '', sorted(list(string))
    dividend = math.factorial(len(tmp)) / 2
    for i in range(len(tmp)):
        perms = math.factorial(len(tmp)) / len(tmp)
        if len(tmp) == 1:
            ans += tmp[0]
            break
        letter = tmp[math.ceil(dividend / perms) - 1]
        ans += letter
        tmp.remove(letter)
        dividend -= perms * (math.floor(dividend / perms))
    print(len(string))
    return ans

Here are some basic inputs

Test.describe("Basic tests")
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")

Answer 1

You're not far from a good answer.

Because of 0 versus 1 indexing, you should start with

dividend = math.factorial(len(tmp)) // 2 - 1

and then you choose a slightly off letter, replace your code with

letter = tmp[dividend // perms]

Also as everything is integer here, it's better to use 'a // b' instead of math.floor(a / b).

All in all, here's a corrected version of your code:

def middle_permutation(string): 
    ans, tmp = '', sorted(list(string)) 
    dividend = math.factorial(len(tmp)) // 2 - 1 
    for i in range(len(tmp)): 
        perms = math.factorial(len(tmp)) // len(tmp) 
        if len(tmp) == 1: 
            ans += tmp[0] 
            break 
        letter = tmp[dividend // perms] 
        ans += letter 
        tmp.remove(letter) 
        dividend -= perms * (dividend // perms) 
    return ans

and just for the beauty of it, a generalization:

def n_in_base(n, base): 
    r = [] 
    for b in base: 
        r.append(n % b) 
        n //= b 
    return reversed(r)

def nth_permutation(s, n):
    digits = n_in_base(n, range(1, len(s)+1))
    alphabet = sorted(s)
    return ''.join(alphabet.pop(ri) for ri in digits)

def middle_permutation(s):
    return nth_permutation(s, math.factorial(len(s)) // 2 - 1)