четверг, 15 марта 2012 г.

Генерация следующего и предыдущего размещения без повторений за O(N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

На текущий момент мы умеем генерировать следующее размещение в лексикографическом порядке со сложностью O(N*N) и O(N*log(N)). Сегодня сделаем эту операцию с линейной сложностью. Для этого нужно будет вспомнить алгоритм генерации следующей перестановки в лексикографическом порядке. Для удобства я буду пользовать STL’ным аналогом next_permutation. Итак начнем по порядку.

Пусть n = 9, m = 5. В качестве алфавита будем использовать цифры от 1 до 9. Рассмотрим текущее размещение Pi = {1,2,4,9,8}. Найдем следующее размещение Pi+1 в лексикографическом порядке.
Поставим во взаимно-однозначное соответствие текущему размещению Pi перестановку Permi, префикс которой равен Pi, а постфикс формируется из оставшихся минимальных элементов алфавита, не использованных в Pi.

Permi 124983567 Формируем перестановку Permi.
124987653 Реверсируем хвост перестановки
Permi+1 125346789 Генерируем следующую перестановку в лексикографическом порядке.

Получив перестановку Permi+1, отбрасываем хвост и получаем следующее размещение Pi+1= {1,2,5,3,4}.
Если на каком-то этапе не получилось сгенерировать следующую перестановку, значит на текущем этапе обрабатывалось последнее размещение в лексикографическом порядке.

  1. bool next_placement(string &perm, int m) {
  2.   reverse(perm.begin()+m, perm.end());
  3.   return next_permutation(perm.begin(), perm.end());
  4. }
* This source code was highlighted with Source Code Highlighter.

Т.к. выполнение реверса хвоста и генерация следующей перестановки имеют сложность O(N), то и генерация следующего размещения так же будет иметь линейную сложность.
Полная реализация: здесь

Генерация предыдущего размещения выполняется таким же образом.

  1. bool prev_placement(string &perm, int m) {
  2.   reverse(perm.begin()+m, perm.end());
  3.   return prev_permutation(perm.begin(), perm.end());
  4. }
* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

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

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