Часть 2. Генерация перестановок без повторений. Episode 2

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

Теория:
1. Окулов. Программирование в алгоритмах. 2004.
2. Липский. Комбинаторика для программистов. 1988
3. Кнут. Том 4. Выпуск 2. Генерация всех кортежей и перестановок. 2008

Рассмотрим две задачи:
1) Генерация следующей перестановки в лексикографическом порядке
2) Генерация всех перестановок с помощью транспозиции двух соседних элементов.

В книге Липского описан алгоритм, генерирующий все перестановки с помощью транспозиций двух элементов(не обязательно соседних).

Практика:
Как и в первой части будем решать задачу 2B-Перестановки

1) Генерация следующей перестановки в лексикографическом порядке(next_permutation).
Данный подход очень хорошо описан в книге Окулова, а также его подробное описание можно найти в книге Кнута(алгоритм L).

1. bool next_permutation(string &a) {
2.  
3.   int j = n-2;
4.   while (j!=-1 && a[j] > a[j+1]) j--;
5.   if (j == -1)
6.     return false; // a - last permutation
7.   int k = n - 1;
8.   while (a[j] > a[k]) k--;
9.  
10.   swap(a[j],a[k]);
11.  
12.   // reverse back [j+1, n-1]
13.   int l = j + 1, r = n - 1;
14.   while (l<r)
15.     swap(a[l++],a[r--]);
16.   return true;
17. }

* This source code was highlighted with Source Code Highlighter.

Отметим тот факт, что изначально перестановка a должна быть минимальной, т.е. необходимо отсортировать элементы перестановки в порядке возрастания.
[Решение]

2)Генерация всех перестановок с помощью транспозиции двух соседних элементов
Опять же направляю в книгу Окулова, в котором имеется превосходное описание данного алгоритма на основе таблицы инверсий:

[Решение]