Задача
Перестановка – это упорядоченная выборка объектов. К примеру, 3124 является одной из возможных перестановок из цифр 1, 2, 3 и 4. Если все перестановки приведены в порядке возрастания или алфавитном порядке, то такой порядок будем называть словарным. Словарные перестановки из цифр 0, 1 и 2 представлены ниже:
012 021 102 120 201 210
Какова миллионная словарная перестановка из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?
Решение
Всегда радует, как решают подобные задачи питонисты. У них есть библиотека, которую надо просто вызвать и она сама всё сделает. И они такие: ура, задача решена :)
В общем, мне доставили хлопот перестановки, которые надо было реализовать вручную. Я медитировал три дня, рисуя различные схемы, и наконец решение ко мне пришло. Вот только не знаю, смогу ли его внятно объяснить, мне кажется, на это понадобится ещё три дня :)
Читайте также:
Давайте для начала рассмотрим строку попроще "123".
Я ввёл для себя два термина: финальная перестановка и рекурсивная перестановка.
Финальная перестановка всегда происходит в последних двух разрядах строки и мы знаем, что переставить их можно только один раз. Например, строка 123 переставляется в двух последних разрядах и получается 1[32]. Больше там переставлять нечего, все варианты уже перебраны.
Обратите внимание, что после перестановки всё сразу возвращается как было. Это нужно для того, чтобы правильно работали следующие перестановки. Пока выглядит бессмысленно, но именно в этом месте будет проверка на достижение нужного значения, которую я убрал для краткости.
Теперь рассмотрим три последних разряда: 123. Так как их три, финальная перестановка невозможна. Поэтому я отрезаю старший и рекурсивно вызываю перестановку с оставшимися двумя. Как нетрудно догадаться, она будет финальной.
permute_recursive(str, len, group_size - 1);
Затем я меняю старший разряд по очереди с каждым из двух.
Т.е. получаю 2[13] и 3[12]. Каждое из этих значений во-первых является самостоятельной перестановкой, а во-вторых проходит рекурсивную перестановку, получая 2[31] и 3[21]. Итого:
123, 132, 213, 231, 312, 321
Теперь можно экстраполировать этот пример на весь алгоритм.
В строке 0123456789 размер перестановочной группы равен 10 (с 0 по 9). Но так как эта группа не финальная, то уменьшаем размер группы и делаем рекурсивную перестановку (рекурсивная с 1 по 9 (рекурсивная с 2 по 9 (рекурсивная с 3 по 9 (... и финальная с 8 по 9))).
Затем (мы вернулись из рекурсий) первый символ в группе (0) переставляем местами по очереди с остальными символами и снова отправляем группу в рекурсию. И помните, что в рекурсиях будет свой первый символ группы, который тоже будет по очереди меняться с остальными и т.д.
Тут нужно заметить, что в группе символы изначально идут по возрастанию, поэтому перебираются просто по порядку. Но есть нюанс.
Допустим, в группе 789 мы меняем 7 и 8. Получилось 879, где 79 идут по порядку. Но далее поменяем 7 и 9, и получим 987, а должно быть 978.
Поэтому замену надо делать так, чтобы заменяющий символ всегда вставлялся в первую позицию оставшейся группы (он берётся из старшего разряда и поэтому всегда меньше остальных в группе). Для этого на место заменяемого символа нужно сдвинуть все символы, которые левее его.
А при восстановлении, соответственно, сдвинуть их обратно на свои места.
И... в целом всё, только я добавил еще счётчик перестановок, который увеличивается на 1 после каждой перестановки. Самая первая строка это тоже перестановка, поэтому счётчик начинается с 1 (я на этом прокололся).
И также добавил условия, которые после каждой перестановки проверяют счётчик. Так как эти условия пришлось писать в нескольких местах, я убрал их из иллюстраций, но они есть в полной версии кода.
Ссылка на онлайн-компилятор языка C с текстом программы
Оптимизация
Несмотря на миллион перестановок, программа выдаёт результат мгновенно. Смысла в оптимизации не вижу, так как задача всё равно без практического применения. Но если её делать, то стоит обратить внимание вот на что:
Число перестановок из n разрядов это n!. Чтобы в строке 0123456789 первый символ 0 заменился на 1, нужно полностью перебрать всё, что после 0, это будет 9! перестановок, или 362880. Чтобы 0 заменился на 2, нужно ещё столько же.
Итого получим строку 2013456789 на 725761-й перестановке. Легко видеть, что такую строку можно вычислить сразу, переставив два раза 0 в группе 0123456789 и задав счётчик перестановок 1+9!*2.
Потом уже продолжать перестановки с этого состояния, добивая счётчик до миллиона. Если оптимизировать дальше, то можно добивать счётчик и более мелкими группами, например 8! это 40320, и таким образом максимально быстро приближать к миллиону.
Подборка всех задач:
