Часть 4. Генерация перестановки по номеру и получение номера по перестановке

[Все темы по перестановкам]

Теория: Окулов. Программирование в алгоритмах. 2004.

Рассмотрим две задачи:
1) Генерация перестановки по номеру
2) Получение номера по перестановке

Генерация перестановок происходит в лексикографическом порядке. Нумерация перестановок начинается с единицы.

Практика: 
Обе задачи реализуем на основе problem Перестановка по номеру.

1) Генерация перестановки по номеру
Вся необходимая теория довольно популярно изложена в книге Окулова. Остановлюсь на некоторых моментах. Перестановку будем последовательно получать слева направо. Сначала мы имеем N пустых позиций перестановки. Если выписать в столбец все перестановки в лексикографическом порядке то увидим, что их можно разбить на N групп размерностью по (N-1)! каждая. Зная номер перестановки можно без проблем определить в какую группу она попадет. Номер группы и уже полученное начало перестановки однозначно определяют текущий элемент перестановки.
Общую логику передает функция permutation_by_num:

1. int fact[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,  39916800, 479001600};
2. int notUsed(vector<bool> &used, int blockNum) {
3.  
4.   int j, pos = 0;
5.   for (j = 1; j < used.size(); j++) {
6.     if (!used[j]) pos++;
7.     if (blockNum == pos)
8.       break;
9.   }
10.   return j;
11. }
12. vector<int> permutation_by_num(int n, int num) {
13.  
14.   vector<int> res(n); 
15.   vector<bool> used(n+1,false);
16.  
17.   for (int i = 0; i < n; i++) {
18.     int blockNum = (num - 1) / fact[n - i - 1] + 1;
19.     int j = notUsed(used, blockNum);
20.     res[i] = j;
21.     used[j] = true;
22.     num = (num - 1) % fact[n - i - 1] + 1;
23.   }
24.   return res;
25. }

* This source code was highlighted with Source Code Highlighter.

[Решение]

2) Получение номера по перестановке
Для решения этой задачи в первую очередь нужно понять принцип решения первой задачи, а потом проделать обратные манипуляции.
Мне не удалось найти problem, которая в чистом виде решает поставленную задачу. Но у нас есть problem Перестановка по номеру, на основе которой можно проверить правильность решения этой задачи.

[Решение]