107
правок
Изменения
Новая страница: «== Алгоритм == {{Определение|definition= '''Получение предыдущего объекта''' {{---}} это нахождение о...»
== Алгоритм ==
{{Определение|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>
* Дописываем максимально возможный хвост из единиц
'''int[]''' nextVector('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина вектора</font>
'''while''' (n >= 0) '''and''' (a[n] != 1)
a[n] = 1
n--
'''if''' n == -1
'''return''' ''null''
a[n] = 0
'''return''' a
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
{{Определение|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>
* Дописываем максимально возможный хвост из единиц
'''int[]''' nextVector('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина вектора</font>
'''while''' (n >= 0) '''and''' (a[n] != 1)
a[n] = 1
n--
'''if''' n == -1
'''return''' ''null''
a[n] = 0
'''return''' a
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
