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

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

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

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

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

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

Получив перестановку Perm_i+1, отбрасываем хвост и получаем следующее размещение P_i+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.

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