Как я могу вычислить n-ю перестановку (или рассказать лексикографический порядок данной перестановки)?

Question

Этот вопрос состоит из двух частей, хотя, поскольку я пытаюсь приспособиться к реализации Prolog, решение одного из них, вероятно, немедленно приведет к решению другого.

1. Учитывая перестановку из списка целых чисел {1,2,...,N}, как я могу сказать, что индекс этой перестановки в лексикографическом порядке?
2. Предоставлено число k, как я могу рассчитать k-я перестановка чисел {1,2...,N}?

Я ищу алгоритм, который может сделать это разумно лучше, чем просто итерация next permutation функцию k раз. Afaik должно быть возможно напрямую вычислить оба из них.

Что я додумал до сих пор, так это то, что, глядя на цифры слева, я могу сказать, сколько перестановок было перед каждым номером в определенном индексе, а затем каким-то образом их объединить, но я не совсем уверен, это приводит к правильному решению.

Answer 1

Я просто дать набросок решения для каждого:

Учитывая перестановку из списка целых чисел {1,2, ..., N}, как я могу сказать, что это индекс этой перестановки в лексикографическом порядке?

Для этого спросите себя, сколько позиций начинается с 1? Есть (N - 1)!. Теперь, давайте сделаем пример:

3 1 2 

Сколько перестановок 1 2 3 начала с 1 или 2? 2*2!. Это должно быть после этого, поэтому его индекс составляет не менее 2*2! = 4. Теперь проверьте следующий элемент. Сколько перестановок 1 2 начинаются с 0? Никто. Вы закончили, индекс 4. Вы можете добавить 1, если вы хотите использовать индексацию 1.

Учитывая число k, как можно вычислить k-ю перестановку чисел {1,2 ..., N}?

Предоставлено 4, как мы можем получить 3 1 2? Мы должны найти каждый элемент.

Что мы можем иметь на первом месте?Если у нас есть 1, максимальный индекс может быть 2! - 1 = 1 (я использую нулевую индексацию). Если у нас есть 2, максимум может быть 2*2! - 1 = 3. Если у нас есть 3, максимум может быть 5. Таким образом, мы должны иметь 3:

3 

Теперь мы свели задачу к нахождению 4 - 2*2! = 0 ей перестановки 1 2, которая 1 2 (вы можете рассуждать о нем рекурсивно, как указаны выше).

Answer 2

Подумайте, сколько перестановок начинается с числа 1, сколько начинается с числа 2 и т. Д. Скажем, n = 5, тогда 24 перестановки начинаются с 1, 24 начинается с 2 и так далее. Если вы ищете перестановку, скажите k = 53, есть 48 перестановок, начиная с 1 или 2, поэтому # 53 является пятой из перестановок, начиная с 3.

Из перестановок, начинающихся с 3, 6, начинаются с 31 , 32, 34 или 35. Таким образом, вы ищете пятую перестановку, начиная с (3, 1). Есть две перестановки, каждая из которых начинается с 312, 314 и 315. Итак, вы ищете первую из двух перестановок, начиная с 315. Что такое 31524.

Должно быть достаточно легко превратить это в код.

Answer 3

Вы также можете взглянуть на систему факториалов, особенно часть относительно permutations. Для данного номера k вы должны сначала найти его факториальное представление, которое тогда легко дает требуемую перестановку (фактически, (k+1) -st перестановка).

Пример k=5 и номер {1,2,3}:

5 = 2 * 2! + 1 * 1! + 0 * 0! = (210) _!

так что факториальное представление 5 равно 210. Теперь перечислим это представление в подстановку. Начнем с упорядоченного списка (1,2,3). Самая левая цифра в нашем факториальном представлении равна 2, поэтому мы ищем элемент в списке в индексе 2, который равен 3 (список индексируется нулем). Теперь мы оставляем список (1,2) и продолжаем процедуру. Самая левая цифра в нашем факториальном представлении после удаления 2 равна 1, поэтому мы получаем элемент в индексе 1, который равен 2. Наконец, мы остаемся с 1, поэтому перестановка (k+1) -st (6) 2,3} - {3,2,1}.

Несмотря на то, что для его понимания требуется некоторое время, это довольно эффективный алгоритм и прост в программировании. Обратное отображение аналогично.