Часть 3. Генерация перестановок с повторениями

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

Теория:
1. Меньшиков. Олимпиадные задачи по программированию. 2006
2. Окулов. Дискретная математика. Теория и практика решения задач по информатике. 2008
3. Кнут. Том 4. Выпуск 2. Генерация всех кортежей и перестановок. 2008

Рассмотрим три задачи:
1) Рекурсивный способ генерации всех перестановок с повторениями в лексикографическом порядке
2) Генерация следующей перестановки с повторениями в лексикографическом порядке(next_permutation)
3) Генерация предыдущей перестановки с повторениями в лексикографическом порядке(prev_permutation)

Практика:
Все задачи будем решать на основе 3B-Перестановки(2)

Аналогичные алгоритмы, реализованные ранее относительно перестановок без повторений неприемлемы для перестановок с повторениями.  Обратное неверно. Поэтому реализация для предложенных выше задач будет универсальной и будет работать для перестановок без повторений.

1) Рекурсивный способ генерации всех перестановок с повторениями в лексикографическом порядке.
Суть реализации взята из авторского разбора задачи 3B.
[Решение]
2) Генерация следующей перестановки с повторениями в лексикографическом порядке(next_permutation)

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.

Данная реализация очень напоминает аналогичную функцию относительно перестановок без повторения. Если хорошенько присмотреться, то строгое сравнение в строках 4 и 8 теперь стало нестрогим.
[Решение]
3) Генерация предыдущей перестановки с повторениями в лексикографическом порядке(prev_permutation)

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

* This source code was highlighted with Source Code Highlighter.

Здесь нужно грамотно обратить все действия, которые использовались при генерации следующей перестановки.
[Решение]