Позвольте мне переформулировать проблему, которую, я думаю, вы имеете в виду.
У вас есть битовая строка длиной n-1. Если его цифры представляют собой шаблон увеличения / уменьшения, это описывает набор перестановок, которые соответствуют шаблону. Этот набор можно поставить в порядке возрастания.
Вы хотите иметь возможность решить две проблемы.
- Учитывая перестановку, которая соответствует шаблону, скажите, где он находится в этом порядке (то есть "оцените" его)
- Учитывая число, произведите перестановку, которая находится в том месте в заказе (то есть, "unrank" это)
И в идеале вы хотели бы иметь возможность решить их без необходимости генерировать все перестановки, которые соответствуют шаблону.
Ключом к обоим является следующая функция:
def count_matching (bitstring, start):
''' Returns how many permutations of 1..(len(bitstring) + 1)
''' match bitstring with starting value start
# some implementation here.
Это можно довольно легко вычислить рекурсивно. Однако, делая это, наивный способ порождает все перестановки. Но если мы добавим кеширующий слой к memoize этому, то мы храним полиномиальный объем данных и делаем полиномиальное количество вызовов, чтобы заполнить его.
Вот данные, которые вы получаете, когда они кешируются для вашего примера:
{
('010', 1): 2,
('010', 2): 2,
('010', 3): 1,
('010', 4): 0,
('10', 1): 0,
('10', 2): 1,
('10', 3): 1,
('0', 1): 1,
('0', 2): 0,
('', 1): 1
}
Теперь это похоже на большое количество данных для небольшого количества паттернов. Но для перестановки длиной n количество записей увеличивается как O(n^2), а количество вызовов для заполнения увеличивается как O(n^3). (Любой читатель с орлиными глазами может выяснить, как его заполнить вовремя O(n^2). Я собираюсь с простой версией.)
Имея это в виду, мы можем взять ранг и выяснить, какой должна быть перестановка, исходя из следующей идеи.
Предположим, что мы хотим найти перестановку ранга 4. Наш начальный список чисел (1 2 3 4). Мы можем пропустить 0 перестановок, которые начинаются с ('010', 1), и ответом будет второе из 2 с ('010', 2).
Возьмем второе число 2, и наша частичная перестановка будет [2, и у нас есть числа (1 3 4). Мы ищем 2-й для цепочки битов '10'. Мы пропускаем 0 перестановок, которые начинаются с ('10', 1), 1 с ('10', 2) и хотим получить первое из 1 с ('10', 3).
Возьмите третье число 4, и наша частичная перестановка будет [2, 4, и у нас есть числа (1 3). Как и прежде, мы обнаруживаем, что мы хотим получить первое из 1 с ('0', 1).
Возьмите первое число 1, и наша частичная перестановка будет [2, 4, 1, и у нас есть числа (3). Выборов не так много.
Итак, мы заканчиваем и получаем [2, 4, 1, 3]. Что вы можете проверить это 4-й.
И так мы заканчиваем с [2, 4, 3, 1].
Мы также можем пойти другим путем. Взяв ту же перестановку, мы начинаем с [2, 4, 3, 1] и хотим получить его ранг.
Сколько перед ним, которые отличаются первой цифрой? Он использовал 2-й возможный первый номер. Из записи для ('010', 1) мы знаем, что их 2. И оставшиеся цифры: 1 3 4.
Сколько перед ним, которые отличаются второй цифрой? Он использует 3-й возможный второй номер. Из записей для ('10', 1) и ('10', 2) мы знаем, что перед ним еще 1.
Теперь у нас есть номера 1 3. Никто не дошел до него в третьей цифре. И опять ни одного в последнем.
С 3 перед ним, он должен иметь ранг 4.
И вот оно у вас. Для запоминания одной рекурсивной функции вы теперь можете легко найти перестановки по рангу или ранжировать данную перестановку.