Напишу два способа решения проблемы.
Первый. Для нахождения средней перестановки строки из 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". Подробности этого алгоритма
здесь 
