вторник, 8 февраля 2011 г.

Часть 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.

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

Комментариев нет:

Отправить комментарий