== Алгоритм ==
{{Определение|definition= '''Получение предыдущего объекта''' {{---}} это нахождение объекта, предшествующего данному в [[Лексикографический порядок|лексикографическом порядке]].
}}
Объект <tex>Q</tex> называется предыдущим за <tex>P</tex>, если <tex>P < Q</tex> и не найдется такого <tex>R</tex>, что <tex>P < R < Q</tex>.

Отсюда понятен алгоритм:
* находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,
* к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),
* дописываем максимально возможный хвост.
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.

== Специализация алгоритма для генерации предыдущего битового вектора ==
* Находим минимальный суффикс, в котором есть <tex>1</tex>, его можно уменьшить, не изменяя оставшейся части
* Вместо <tex>1</tex> записываем <tex>0</tex>
* Дописываем максимально возможный хвост из единиц

'''Пример:'''
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevbitvector.png|200px|thumb|искомый суффикс, преобразование]]
|}
===Реализация===

'''int[]''' prevVector('''int[]''' a): // <tex>n</tex> {{---}} длина вектора
'''while''' (n >= 0) '''and''' (a[n] != 1)
a[n] = 1
n--
'''if''' n == -1
'''return''' ''null''
a[n] = 0
'''return''' a
Приведённый алгоритм эквивалентен вычитанию единицы из битового вектора.

== Специализация алгоритма для генерации предыдущей перестановки ==
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
* Меняем его с максимальным элементом, меньшим нашего, стоящим правее
* Перевернем правую часть

'''Пример:'''
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevperm.png|600px|thumb|искомый суффикс (убывающая последовательность), элемент нарушающий последовательность, преобразование]]
|}
===Реализация===
'''int[]''' prevPermutation('''int[]''' a): // <tex>n</tex> {{---}} длина перестановки
'''for''' i = n - 2 '''downto''' 0
'''if''' a[i] > a[i + 1]
max = i + 1
'''for''' j = i + 1 '''to''' n - 1
'''if''' (a[j] < a[max]) '''and''' (a[j] < a[i])
max = j
swap(a[i], a[j])
reverse(a, i + 1, n - 1)
'''return''' a
'''return''' ''null''
===Мультиперестановка===
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.

== Специализация алгоритма для генерации предыдущего сочетания ==

* Проходя справа налево, находим элемент <tex>t</tex> так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом <tex>0</tex> равен <tex>0</tex>, а первый элемент хранится в <tex>1</tex>)
* уменьшаем его на единицу
* дописываем максимально возможный хвост
Если элемента <tex>t</tex> не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.

Пусть массив <tex>a</tex> хранит сочетания так, что первый элемент хранится в <tex>a[1]</tex>

'''Пример:'''
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:PrevChoose.png|600px|thumb|сочетания из n по k, элемент, который уменьшаем, максимальный хвост, преобразование]]
|}
===Реализация===
'''int[]''' prevChoose('''int[]''' a): // <tex>n</tex> {{---}} количество различных элементов
a[0] = 0 // <tex>k</tex> {{---}} длина сочетания
'''for''' i = k '''downto''' 1
'''if''' a[i] - a[i - 1] > 1
a[i]--
t = max(a[i] + 1, n - (k - i) + 1)
'''for''' j = i + 1 '''to''' k
a[j] = t
t++
'''return''' a
'''return''' null

== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядочено по возрастанию.

Рассмотрим два случая:

<tex> 1) </tex> Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на <tex>1</tex>, так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.

<tex> 2) </tex> Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое точно больше предыдущего на <tex>1</tex>. Обозначим его номер за <tex>j</tex>. Тогда <tex> a[j] = a[j] - 1 </tex>, а <tex> a[j + 1] = 1 + \sum_{i = j + 1}^n a[i] </tex>. А <tex> a[j + 1] </tex> будет последним слагаемым в разбиении.

'''Пример:'''

Случай <tex>1</tex>:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevpart1.png|600px|thumb|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]
|}
Случай <tex>2</tex>:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevpart2.png|600px|thumb|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]
|}
=== Реализация ===
Первое слагаемое находится под индексом <tex>1</tex>.

'''list<int>''' prevPartition('''list<int>''' a):
a[0] = 0
'''if''' a[a.size - 1] / 2 >= a[a.size - 2]
k = a[a.size - 1]
a[a.size - 1] = a[a.size - 2] / 2
a.push_back(k - a[a.size - 1])
'''return''' a
'''else'''
sum = a[a.size - 1];
'''for''' i = a.size '''downto''' 1
'''if''' (i == 1) '''and''' (a[1] == 1)
'''return''' null
'''if''' a[i] > a[i - 1]
a[i]--
a[i + 1] = sum + 1
n = i + 1
'''return''' a
'''else'''
sum += a[i]
a.pop_back();

== См. также ==
* [[Получение объекта по номеру]]
* [[Получение номера по объекту]]
* [[Получение следующего объекта]]

Получение предыдущего объекта

2014-12-30T20:42:43Z

Flanir: /* Специализация алгоритма для генерации предыдущего разбиения на слагаемые */

== Алгоритм ==
{{Определение|definition= '''Получение предыдущего объекта''' {{---}} это нахождение объекта, предшествующего данному в [[Лексикографический порядок|лексикографическом порядке]].
}}
Объект <tex>Q</tex> называется предыдущим за <tex>P</tex>, если <tex>P < Q</tex> и не найдется такого <tex>R</tex>, что <tex>P < R < Q</tex>.

Отсюда понятен алгоритм:
* находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,
* к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),
* дописываем максимально возможный хвост.
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.

== Специализация алгоритма для генерации предыдущего битового вектора ==
* Находим минимальный суффикс, в котором есть <tex>1</tex>, его можно уменьшить, не изменяя оставшейся части
* Вместо <tex>1</tex> записываем <tex>0</tex>
* Дописываем максимально возможный хвост из единиц

'''Пример:'''
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevbitvector.png|200px|thumb|искомый суффикс, преобразование]]
|}
===Реализация===

'''int[]''' prevVector('''int[]''' a): // <tex>n</tex> {{---}} длина вектора
'''while''' (n >= 0) '''and''' (a[n] != 1)
a[n] = 1
n--
'''if''' n == -1
'''return''' ''null''
a[n] = 0
'''return''' a
Приведённый алгоритм эквивалентен вычитанию единицы из битового вектора.

== Специализация алгоритма для генерации предыдущей перестановки ==
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
* Меняем его с максимальным элементом, меньшим нашего, стоящим правее
* Перевернем правую часть

'''Пример:'''
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevperm.png|600px|thumb|искомый суффикс (убывающая последовательность), элемент нарушающий последовательность, преобразование]]
|}
===Реализация===
'''int[]''' prevPermutation('''int[]''' a): // <tex>n</tex> {{---}} длина перестановки
'''for''' i = n - 2 '''downto''' 0
'''if''' a[i] > a[i + 1]
max = i + 1
'''for''' j = i + 1 '''to''' n - 1
'''if''' (a[j] < a[max]) '''and''' (a[j] < a[i])
max = j
swap(a[i], a[j])
reverse(a, i + 1, n - 1)
'''return''' a
'''return''' ''null''
===Мультиперестановка===
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.

== Специализация алгоритма для генерации предыдущего сочетания ==

* Проходя справа налево, находим элемент <tex>t</tex> так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом <tex>0</tex> равен <tex>0</tex>, а первый элемент хранится в <tex>1</tex>)
* уменьшаем его на единицу
* дописываем максимально возможный хвост
Если элемента <tex>t</tex> не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.

Пусть массив <tex>a</tex> хранит сочетания так, что первый элемент хранится в <tex>a[1]</tex>

'''Пример:'''
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:PrevChoose.png|600px|thumb|сочетания из n по k, элемент, который уменьшаем, максимальный хвост, преобразование]]
|}
===Реализация===
'''int[]''' prevChoose('''int[]''' a): // <tex>n</tex> {{---}} количество различных элементов
a[0] = 0 // <tex>k</tex> {{---}} длина сочетания
'''for''' i = k '''downto''' 1
'''if''' a[i] - a[i - 1] > 1
a[i]--
t = max(a[i] + 1, n - (k - i) + 1)
'''for''' j = i + 1 '''to''' k
a[j] = t
t++
'''return''' a
'''return''' null

== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядочено по возрастанию.

Рассмотрим два случая:

<tex> 1) </tex> Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на <tex>1</tex>, так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.

<tex> 2) </tex> Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое точно больше предыдущего на <tex>1</tex>. Обозначим его номер за <tex>j</tex>. Тогда <tex> a[j] = a[j] - 1 </tex>, а <tex> a[j + 1] = 1 + \sum_{i = j + 1}^n a[i] </tex>. А <tex> a[j + 1] </tex> будет последним слагаемым в разбиении.

'''Пример:'''

Случай 1:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevpart1.png|600px|thumb|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]
|}
Случай 2:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:Prevpart2.png|600px|thumb|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]
|}
=== Реализация ===
Первое слагаемое находится под индексом <tex>1</tex>.

'''list<int>''' prevPartition('''list<int>''' a):
a[0] = 0
'''if''' a[a.size - 1] / 2 >= a[a.size - 2]
k = a[a.size - 1]
a[a.size - 1] = a[a.size - 2] / 2
a.push_back(k - a[a.size - 1])
'''return''' a
'''else'''
sum = a[a.size - 1];
'''for''' i = a.size '''downto''' 1
'''if''' (i == 1) '''and''' (a[1] == 1)
'''return''' null
'''if''' a[i] > a[i - 1]
a[i]--
a[i + 1] = sum + 1
n = i + 1
'''return''' a
'''else'''
sum += a[i]
a.pop_back();

== См. также ==
* [[Получение объекта по номеру]]
* [[Получение номера по объекту]]
* [[Получение следующего объекта]]