Клай

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

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

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

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 символах. Посему полагаю алгоритм верный, но операции вычисления надо организовывать по другому. Возможно вручную написать.

a = [j for i in A if isinstance(i, tuple) for j in i]

Не делайте массив аккумуляторов того же разрешения, что и исходник - возьмите четверть. Это первый вариант.

Второй вариант - считайте градиент в каждой точке. Где он ближе к 0, там и максимум.

хорошо бы профилирование