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

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

Теория:
1) Липский. Комбинаторика для программистов. 1988
2) Меньшиков. Олимпиадные задачи по программированию. 2006.

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

Для начала разберемся, что такое лексико- и антилексико-графические порядки.
Начальная перестановка: {1, 2, 3}

№	Лексикографический	Антилексикографический
0	1 2 3	1 2 3
1	1 3 2	2 1 3
2	2 1 3	1 3 2
3	2 3 1	3 1 2
4	3 1 2	2 3 1
5	3 2 1	3 2 1

Напомним, что лексикографический порядок – это порядок слов, который используется в словарях.
Слово A меньше слова B, если первые i символов слов равны, а символ A[i+1] < B[i+1]. Отсюда вытекает следствие, что если слово А является началом слова B, то A < B.

Антилексикографический порядок отличается от лексикографического только тем, что сравнение символов идет справа налево.
Слово A меньше слова B, если последние i символов равны, а символ A[i-1] < B[i-1]. Также следует, что если слово B заканчивается на слово A, то A < B.

Практика:
Решим задачу 2B-Перестановки из задачника Федора Меньшикова двумя рассматриваемыми способами.
Как можно было заметить, оба порядка начинаются с минимальной перестановки {1, 2, 3} и заканчивается максимальной {3, 2, 1}.

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

1. int n;
2. vector<int> p;
3. vector<bool> used;
4. string str;
5. ...
6. void lex(int pos)
7. {
8.   if (pos == n) {
9.     for (int i=0;i<n;i++)
10.       cout<<str[p[i]];
11.     cout<<endl;
12.     return;
13.   }
14.   for (int i=0;i<n;i++) {
15.     if (!used[i]) {
16.       used[i] = true;
17.       p[pos] = i;
18.  
19.       lex(pos+1);
20.      
21.       p[pos] = 0; // debug only
22.       used[i] = false;
23.     }
24.   }
25. }

* This source code was highlighted with Source Code Highlighter.

Рекурсивная функция lex(n) генерируется все перестановки из алфавита {0,1,..n-1} длиной n и хранит текущую перестановку в массиве p. Если номер текущей позиции pos == n, тогда сгенерирована следующая перестановка.
[Решение]

2) Генерация всех перестановок в антилексикографическом порядке
Решение полностью идентично, за исключением того, что перестановка формируется с конца
[Решение]