Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

Question

[Клай]

Всем привет. На CodeWars столкнулся с задачкой:

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

Просто выводить все перестановки и искать медианную не катит, так как это очень долго по времени. За основу алгоритма положена идея изложенная здесь https://stackoverflow.com/questions/49037994/execu...

Но моя проблема заключается в том, что код проходит все тесты, за исключением тех случаев, когда длина строчки равна 23,24,25. Выдает следующие ошибки:

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

Вот мой код:

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

Подскажите, пожалуйста, где лажаю и как это исправить. Спасибо)

Comments

[Дмитрий]

Уместнее добавить тэг Алгоритмы, вопрос то не по питону

[Клай]

Дмитрий, Спасибо, сейчас исправлю

Answer 1

[Wataru]

Немного пальцем в небо, но попробуйте заменить "/" на "//". Вам же надо в целых числах считать. Возможно, питон пытается блинные числа приводить к даблу и потом назад к длинными и теряет точность.

Вместо ceil(a/b) используйте (a+b-1)//b
Вместо floor(a/b) или, когда делится без остатка используйте a//b

В логике решения ошибки я не вижу.

Comments

[Клай]

Здравствуйте. Подобный совет мне дали и на Gitter (форум CodeWars). Попробую реализовать в ближайшее время и, если сработает, отмечу Ваш комментарий решением)

[Wataru]

Если не пройдет по времени, то можно решить задачу на бумажке руками. Если там строки до сотен символов, то текущее решение может быть слишком медленным.

Если символов четно - то ответ средний символ, а за ним все остальные по убыванию. Например, "cfedba"
Если символов нечетно, то овтет средний символ, предыдущий, а за нимим все остальные по убыванию. например "nmzyxwvutsrqpolkjigfedcba"

[Клай]

Спасибо, Ваш комментарий помог! Не подскажите напоследок, в чем проявляется неточность, если использовать floating point operationы ?

[Wataru]

Клай, флоаты имеют фиксированное количество бит, а целые в питоне - неограниченное. Поэтому для достаточно больших чисел флоаты начнут округлять и хранить лишь сколько-то ведущих разрядов.

Но это в питоне. В какой-нибудь java пришлось бы использовать специальный BigInt, потому что стандартные целые тоже фиксированной длины.

Answer 2

[Дмитрий]

Клай, Я написал такой вот алгоритм

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

У меня он тоже проходит все тесты до определенной длины, а потом глючит, я боюсь тут что-то с вычислением факториала. Возможно длина числа слишком велика или что-то в этом духе. 24 знака при 24 символах. Посему полагаю алгоритм верный, но операции вычисления надо организовывать по другому. Возможно вручную написать.

Answer 3

[Егор]

Напишу два способа решения проблемы.

Первый. Для нахождения средней перестановки строки из 4-х символов например "abcd" рассмотрим все возможные перестановки этой строки. Существует 4 блока перестановок:

abcd bacd cabd dabc
abdc badc cadb dacb
acbd bcad cbad dbac
acdb bcda cbda dbca
adbc bdac cdab dcab
adcb bdca cdba dcba

Один начинается с "a", потом "b" и так далее. Заметьте, что средняя перестановка для всего этого - самая последняя в блоке 'b'.

Рассорим подробнее эту перестановку. Видно что буквой "b" идут остальные символы последовательности в обратном порядке. То есть символ "ниже среднего", за которым следуют остальные в обратном алфавитном порядке. Решением будет функция которая возвращает 'b' + 'acd'.Reverse().

Мы только что узнали, как найти среднею перестановку для строки из 4 символов

Для строки "abcde" из 5 символов, после записи всех перестановок по порядку, можно будет заметить, что средняя перестановка - это середина блока "С". Здесь нам поможет описанная выше закономерность которая будет работать для последовательностей и больше 4 символов (здесь стоит доверится чтоб не расписывать все перестановки).

Нам нужен символ "c", за которым следует средняя перестановка четырех символов. Вот и готов алгоритм для строк длинной 5 символов и более: необходимо вызвать рекурсивно нашу функцию- "c" + Recursive("abde").

Решение:

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)

Второй:
Я решил эту задачу через Factoradic

Вот моё решение, оно универсальное можно найти любую произвольную перестановку

Суть в том, что есть зависимость номера перестановки и позиции символа в строке. Для решения комбинаторных задач существует факториальная система представления числа (Factoradic). В этой системе число представлено в виде подразрядных номеров - позиций символов исходной строки после перестановки. Например число 14 в Factoradic будет 2100 (для строки из 5 символов будет 21000, 6 -210000). Что означает что для строки "abcd" 14-ая перестановка будет (считаем от нуля)

ab[c]d - взять второй символ и удалить
[2]100 - Факторадик 14
----------
a[b]d - взять первый символ и удалить
[1]00 - Факторадик 14 в котором удалили 1 позицию
---------
[a]d - взять нулевой символ и удалить
[0]0 -- Факторадик 14 в котором удалили 2 позиции
---------
[d] - взять нулевой символ и удалить
[0] - Факторадик 14 в котором удалили 3 позиции

В итоге получим "cbad". Подробности этого алгоритма здесь

Comments

[Клай]

Спасибо большое, за столь подробное объяснение)