как узнать номер перестановки
Как узнать номер перестановки
пятница, 11 февраля 2011 г.
Часть 4. Генерация перестановки по номеру и получение номера по перестановке
Теория: Окулов. Программирование в алгоритмах. 2004.
Рассмотрим две задачи:
1) Генерация перестановки по номеру
2) Получение номера по перестановке
Генерация перестановок происходит в лексикографическом порядке. Нумерация перестановок начинается с единицы.
Практика:
Обе задачи реализуем на основе problem Перестановка по номеру.
1) Генерация перестановки по номеру
Вся необходимая теория довольно популярно изложена в книге Окулова. Остановлюсь на некоторых моментах. Перестановку будем последовательно получать слева направо. Сначала мы имеем N пустых позиций перестановки. Если выписать в столбец все перестановки в лексикографическом порядке то увидим, что их можно разбить на N групп размерностью по (N-1)! каждая. Зная номер перестановки можно без проблем определить в какую группу она попадет. Номер группы и уже полученное начало перестановки однозначно определяют текущий элемент перестановки.
Общую логику передает функция permutation_by_num:
2) Получение номера по перестановке
Для решения этой задачи в первую очередь нужно понять принцип решения первой задачи, а потом проделать обратные манипуляции.
Мне не удалось найти problem, которая в чистом виде решает поставленную задачу. Но у нас есть problem Перестановка по номеру, на основе которой можно проверить правильность решения этой задачи.
Алгоритм: Как найти следующую лексикографическую перестановку
Если кратко описать, что такое лексикографический порядок — это сортировка в алфавитном порядке. Т.е. последовательность символов — AAA → AAB → AAC → AAD → ……… → WWW — является отсортированной в алфавитном (или в нашем случае лексикографическом) порядке.
Представьте, что у Вас есть конечная последовательность символов, например 0, 1, 2, 5, 3, 3, 0 и Вам необходимо найти все возможные перестановки этих символов. Наиболее интуитивным, но и наибольшим по сложности, является рекурсивный алгоритм, когда мы выбираем первый символ из последовательности, далее рекурсивно выбираем второй, третий итд, до тех пор, пока все символы из последовательности не будет выбраны. Понятно, что сложность такого алгоритма — O(n!).
Но оказывается, что наиболее простой алгоритм генерации всех перестановок в лексикографическом порядке — это начать с наименьшей и многократно вычислять следующую перестановку на месте. Давайте посмотрим как это сделать.
Точно также, как при расчете следующего целочисленного значения, мы должны стараться увеличить правую часть последовательности и оставить левую часть неизменной.
В качестве примера возьмем вышеприведенную последовательность — (0, 1, 2, 5, 3, 3, 0). Чтобы получить последовательность выше оригинальной, достаточно переставить первый и второй элементе местами, но в этом нет необходимости, так как можно переставить второй и и третий и получив более близкую по возрастанию последовательность. что приведет нас к следующей более близкой перестановки итд.
Наиболее оптимальным алгоритмом в этом случае будет следующий:
Это значение и будет следующей лексикографической перестановкой.
Что касается практического применения алгоритма, то за все время моей работы он мне ни разу не понадобился, но на интервью в Uber посчитали иначе :))
Для простоты весь код будет написан на Go и думаю никому не составить труда перевести его на любой другой язык программирования.
Большое спасибо PYXRU и 646f67, что ткнули меня носом в возможную оптимизацию алгоритма — произвести расчет перестановки за линейную сложность просто сделав reverse суффикса.
Анализ алгоритма
Пусть m1 m2… mn – входная перестановка. Обозначим через di количество таких пар ( i, j), что i j и m[ i] > m[ j] (элементы m[ i] и m[ j] образуют инверсию). То есть di равно количеству таких чисел, которые стоят правее от i-ой позиции и меньше m[ i].
Тогда номер перестановки в лексикографическом порядке определяется по формуле:
Для перестановки (2, 1, 3) массив d = (1, 0, 0). Номер перестановки равен 1 * 2! + 1 = 3.
Для перестановки (1, 4, 3, 2) массив d = (0, 2, 1, 0). Номер перестановки равен 0 * 3! + 2 * 2! + 1 * 1! + 1 = 6.
Для перестановки (3, 2, 1, 4) массив d = (2, 1, 0, 0). Номер перестановки равен 2 * 3! + 1 * 2! + 0 * 1! + 1 = 15.
Для лексикографически наименьшей перестановки (1, 2, …, n) массив d = (0, 0, …, 0). Ее номер равен 1, так как все слагаемые кроме последнего равны нулю.
Для лексикографически наибольшей перестановки ( n, n – 1, n – 2, …, 1) массив d = ( n – 1, n – 2, n – 3, …, 0). Ее номер равен ( n – 1) * ( n – 1)! + ( n – 2) * ( n – 2)! + … + 1 * 1! + 1 = n! Эту формулу можно доказать методом математической индукции:
База индукции. 1 = 1!.
Реализация алгоритма
Заполняем массив факториалов чисел.
for (inv = 0, j = i + 1; j
Добавляем к результату значение d i * ( n – i )!