How to solve a problem with CodeWars Simple Fun #159: Middle Permutation?

Question

Python

Hello. On CodeWars I ran into a problem:

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.)

Just displaying all the permutations and looking for the median doesn't work, as it takes a very long time. The algorithm is based on the idea presented here https://stackoverflow.com/questions/49037994/execu...

But my problem is that the code passes all tests, except for those cases when the line length is 23,24,25 . Throws the following errors:

'lzyxvutsrqonmeijhkcafdgb' should equal 'lzyxvutsrqonmkjihgfedcba'
'noabcdefgijklymzustvpxwrq' should equal 'nmzyxwvutsrqpolkjigfedcba'

Here is my 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))
    return ans

Please tell me where I'm wrong and how to fix it. Thank you)

Answer 1

A bit of a thumbs up, but try replacing "/" with "//". You also need to count in integers. Perhaps the python is trying to convert pancake numbers to a double and then back to long ones and loses accuracy.
Instead of ceil(a/b) use (a+b-1)//b
Instead of floor(a/b) or when dividing without a remainder use a//b
I don't see an error in the solution logic.

Answer 2

Clay , I wrote such an algorithm

import math
def middle_permutation(string):
    res, letters = '', sorted(list(string))
    fct = math.factorial(len(letters))
    remained = math.ceil(fct / 2)
    
    while (len(letters)):
        fct /= len(letters)
        cnt = math.ceil(remained/ fct) - 1
        res = res + letters.pop(cnt)
        remained -= fct * cnt 
        if (remained == 0):
            remained = fct
            
    return res

For me, it also passes all tests up to a certain length, and then it fails, I'm afraid there is something wrong with calculating the factorial. Perhaps the length of the number is too large or something like that. 24 characters with 24 characters. Therefore, I believe the algorithm is correct, but the calculation operations must be organized differently. It is possible to write manually.

Answer 3

I will write two ways to solve the problem.
First. To find the average permutation of a string of 4 characters, for example "abcd", consider all possible permutations of this string. There are 4 blocks of permutations:
abcd bacd cabd dabc
abdc badc cadb dacb
acbd bcad cbad dbac
acdb bcda cbda dbca
adbc bdac cdab dcab
adcb bdca cdba dcba
One starts with "a", then "b" and so on. Note that the middle permutation for all of this is the very last one in the 'b' block.
Let's discuss this change in more detail. It can be seen that the letter "b" is followed by the remaining characters of the sequence in reverse order. That is, the "below average" character followed by the rest in reverse alphabetical order. The solution is a function that returns 'b' + 'acd'.Reverse().
We just learned how to find the middle permutation for a 4-character
string For the 5-character string "abcde", after writing all the permutations in order, you will notice that the middle permutation is the middle of the "C" block. Here, the pattern described above will help us, which will work for sequences and more than 4 characters (here it is worth trusting so as not to paint all the permutations).
We want the character "c" followed by the average permutation of the four characters. So the algorithm is ready for strings with a length of 5 characters or more: you need to call our function recursively - "c" + Recursive("abde").
Decision:

def middle_permutation(string):
    s = sorted(string)
    if len(s) % 2 == 0:        
        return s.pop(len(s)//2-1) +''.join(s[::-1])
    else:
        return s.pop(len(s)//2) + middle_permutation(s)

Second:
I solved this problem using Factoradic
Here is my solution , it is universal, you can find any arbitrary permutation.
The bottom line is that there is a dependence of the permutation number and the position of the character in the string. To solve combinatorial problems, there is a factorial number representation system (Factoradic). In this system, the number is represented in the form of subdigit numbers - the positions of the characters of the original string after the permutation. For example, the number 14 in Factoradic will be 2100 (for a string of 5 characters it will be 21000, 6 -210000). Which means that for the string "abcd" the 14th permutation will be (counting from zero)
ab[c]d - take the second character and remove
[2]100 - Factoradic 14
----------
a[b]d - take the first character and delete
[1]00 - Factor 14 in which 1 position was deleted
---------
[a]d - take the null character and delete
[0]0 -- Factor 14 where 2 positions have been removed
---------
[d] - take the null symbol and remove
[0] - Factoradic 14 where 3 positions have been removed
As a result, we get "cbad". The details of this algorithm are here.