Получение следующего объекта
Содержание
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта
- К оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть 0, его можно увеличить, не меняя оставшейся части
- Вместо 0 записываем 1
- Дописываем минимально возможный хвост из нулей
for i = n downto 1
if a[i] == 0
a[i] = 1
for j = i + 1 to n
a[j] = 0
break
Пример работы
| 0 | 1 | 0 | 1 | 1 | исходный битовый вектор |
| ^ | находим элемент 0 (самый правый) | ||||
| 0 | 1 | 1 | 1 | 1 | меняем его на 1 |
| 0 | 1 | 1 | 0 | 0 | меняем элементы правее на нули |
| 0 | 1 | 1 | 0 | 0 | следующий битовый вектор |
Специализация алгоритма для генерации следующей перестановки
- Двигаясь справа налево, находим элаемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
- Меняем его с минимальным элементом, большим нашего, стоящим правее
- Перевернем правую часть
for i = n - 1 downto 1
if a[i] < a[i + 1]
// a[j] = min {a[j] > a[i], где j > i}
swap(a[i], a[j])
reverse(a[i + 1]..a[n])
break
Пример работы
| 1 | 3 | 2 | 5 | 4 | исходная перестановка |
| ^ | находим элемент, нарушающий убывающую последовательность | ||||
| ^ | минимальный элемент больше нашего | ||||
| 1 | 3 | 4 | 5 | 2 | меняем их местами |
| 1 | 3 | 4 | 2 | 5 | разворачивам правую часть |
| 1 | 3 | 4 | 2 | 5 | следующая перестановка |
Специализация алгоритма для генерации следующего разбиения на подмножества
Рассмотрим множество первых n натуральных чисел:
| Определение: |
| Разбиением на множества называется представление множества, как объединения одного или более попарно непересекающихся подмножеств множеств. |
Например, для существуют следующие разбиения:
и т. д., всего таких разбиений для существует 52.
Примечание: и - одно и то же разбиение на подмножества.
Упорядочим все разбиения на множества лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество лексикографически меньше подмножества , если верно одно из следующих условий:
- существует такое, что , , для всех если и только если , и существует такое что ;
- и для всех и \ .
Разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .
Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:
- Будем хранить подмножества с помощью двумерного массива, например, разбиение будет выглядеть так:
| 1 | 2 | 3 |
| 4 | 5 |
- Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных ниже:
- Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. Важное замечание: мы не можем заменить 1ый элемент подмножества, мы можем только удалить его.
- Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
- Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.
// a - матрица, содержащая подмножества
// used - массив, в котором мы храним удаленные элементы
fl = true
for i = n - 1 downto 0
if можем добавить в конец подмножества элемент из used
добавляем
break
for j = a[i].size - 1 downto 0
if можем заменить элемент, другим элементом из массива used
заменяем
fl = true
break
used.add(a[i][j]) // удаляем элемент и добавляем его в массив
if (fl) break
// далее выведем все получившиеся подмножества
sort(used)
for i = 0 to used.size - 1
println(used[i]) // выводим лексикографически минимальных хвост
Пример работы
Рассмотрим следующее разбиение:
| 1 | 2 | 3 |
| 4 | 5 |
1 Шаг:
| 1 | 2 | 3 | |
| 4 | 5 | ||
| ^ | Удалили элемент 5. | ||
| used |
2 Шаг:
| 1 | 2 | 3 | |
| 4 | |||
| ^ | Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой. | ||
| 5 | used |
3 Шаг:
| 1 | 2 | 3 | 4 | |
| ^ | Дополнили первое подмножество элементом 4 | |||
| 5 | used |
4 Шаг:
| 1 | 2 | 3 | 4 | |
| 5 | Дописали лексикографически минимальный хвост | |||
| used |
