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

Часть 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)Генерация всех перестановок с помощью транспозиции двух соседних элементов
Опять же направляю в книгу Окулова, в котором имеется превосходное описание данного алгоритма на основе таблицы инверсий:

[Решение]

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

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