Получение следующего объекта
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта ,
- к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило ),
- дописываем минимальный возможный хвост.
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть , его можно увеличить, не меняя оставшейся части
- Вместо записываем
- Дописываем минимально возможный хвост из нулей
int[] nextVector(int[] a): // — длина вектора
while (n >= 0) and (a[n] != 0)
a[n] = 0
n--
if n == -1
return null
a[n] = 1
return a
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
Пример работы
| 0 | 1 | 0 | 1 | 1 | исходный битовый вектор |
| ^ | начинаем идти с конца | ||||
| 0 | 1 | 0 | 0 | 0 | пока элементы равны 1, заменяем их на 0 |
| 0 | 1 | 1 | 0 | 0 | меняем первый не удовлетворяющий условию цикла элемент на 1 |
| 0 | 1 | 1 | 0 | 0 | следующий битовый вектор |
Специализация алгоритма для генерации следующей перестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
- Меняем его с минимальным элементом, большим нашего, стоящим правее
- Перевернем правую часть
int[] nextPermutation(int[] a): // — длина перестановки
for i = n - 2 downto 0
if a[i] < a[i + 1]
min = i + 1;
for j = i + 1 to n - 1
if (a[j] < a[min]) and (a[j] > a[i])
min = j
swap(a[i], a[min])
reverse(a, i + 1, n - 1)
return a
return null
Пример работы
| 1 | 3 | 2 | 5 | 4 | исходная перестановка |
| ^ | находим элемент, нарушающий убывающую последовательность | ||||
| ^ | минимальный элемент больше нашего | ||||
| 1 | 3 | 4 | 5 | 2 | меняем их местами |
| 1 | 3 | 4 | 2 | 5 | разворачивам правую часть |
| 1 | 3 | 4 | 2 | 5 | следующая перестановка |
Специализация алгоритма для генерации следующей мультиперестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
- Меняем его с минимальным элементом, большим нашего, стоящим правее.
- Переворачиваем правую часть.
int[] nextMultiperm(int[] b): // — длина мультиперестановки
i = n - 2
while (i >= 0) and (b[i] >= b[i + 1])
i--
if i >= 0
j = i + 1
while (j < n - 1) and (b[j + 1] > b[i])
j++
swap(b[i] , b[j])
reverse(b, i + 1, n - 1)
return b
else
return null
Пример работы
| 1 | 2 | 3 | 1 | 2 | 3 | Исходная перестановка. |
| ^ | Находим элемент, нарушающий убывающую последовательность. | |||||
| ^ | Минимальный элемент больше нашего. | |||||
| 1 | 2 | 3 | 1 | 3 | 2 | Меняем их местами. |
| 1 | 2 | 3 | 1 | 3 | 2 | Следующая мультиперестановка. |
Специализация алгоритма для генерации следующего сочетания
- Добавим в конец массива с сочетанием – максимальный элемент.
- Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на и больше.
- Увеличим найденный элемент на , и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
int[] nextChoose(int[] a, int n, int k): // — параметры сочетания
for i = 0 to k - 1
b[i] = a[i]
b[k] = n + 1
i = k - 1
while (i >= 0) and (b[i + 1] - b[i] < 2)
i--
if i >= 0
b[i]++
for j = i + 1 to k - 1
b[j] = b[j - 1] + 1
for i = 0 to k - 1
a[i] = b[i]
return a
else
return null
Пример работы
| 1 | 2 | 5 | 6 | 7 | Дописываем 7 в конец сочетания. |
| 1 | 2 | 5 | 6 | 7 | |
| ^ | Находим элемент i, a[i + 1] - a[ i ] >= 2 | ||||
| 1 | 3 | 5 | 6 | 7 | Увеличиваем его на 1. |
| 1 | 3 | 4 | 5 | 6 | Дописываем минимальный хвост. |
| 1 | 3 | 4 | 5 | Следующее сочетание. |
Специализация алгоритма для генерации следующего разбиения на слагаемые
Рассматриваемый алгоритм находит следующее разбиение на слагаемые, при этом разбиение упорядоченно по возрастанию.
- Увеличим предпоследнее слагаемое на , уменьшим последнее слагаемое на .
- Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
- Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое на два слагаемых и таких, что равно предпоследнему слагаемому, а . Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.
// — список, содержащий разбиение данного числа — его размер list<int> nextPartition(list<int> b): b[b.size - 1]-- b[b.size - 2]++ if b[b.size - 2] > b[b.size - 1] b[b.size - 2] += b[b.size - 1] b.remove(b.size - 1) else while b[b.size - 2] * 2 <= b[b.size - 1] b.add(b[b.size - 1] - b[b.size - 2]) b[b.size - 2] = b[b.size - 3] return b
Пример работы
| 1 | 1 | 7 | Прибавим 1 + 1, вычтем 7 - 1. | ||
| 1 | 2 | 6 | Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4 | ||
| 1 | 2 | 2 | 4 | ||
| 1 | 2 | 2 | 2 | 2 | |
| 1 | 2 | 2 | 2 | 2 | Следующее разбиение на слагаемые числа 9. |
| 1 | 4 | 5 | Прибавим 4 + 1, вычтем 5 - 1. |
| 1 | 5 | 4 | Проверяем: 5 > 4, значит прибавим к 5 + 4. |
| 1 | 9 | 4 | Удалим последний элемент. |
| 1 | 9 | Следующее разбиение на слагаемые числа 10. |
Специализация алгоритма для генерации следующего разбиения на подмножества
Рассмотрим множество первых n натуральных чисел:
Упорядочим все разбиения на множества лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество лексикографически меньше подмножества , если верно одно из следующих условий:
- существует такое, что , , для всех если и только если , и существует такое что ;
- и для всех и \ .
Разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .
Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:
- Будем хранить подмножества в списке списков, например, разбиение будет выглядеть так:
| 1 | 2 | 3 |
| 4 | 5 |
- Будем поддерживать массив удалённых элементов — элементы, которые затем нужно будет вернуть в разбиение.
- Двигаясь снизу вверх будем рассматривать подмножества.
- Если мы можем дописать в текущее подмножество минимальный элемент из удалённых, то мы нашли следующее разбиение и нужно завершить цикл.
- Если дописать не можем, значит, либо нужно укоротить и заменить какой-то элемент в текущем подмножестве, либо перейти к следующему подмножеству. Будем идти справа налево и рассматривать элементы:
- Если мы можем заменить текущий элемент минимальным удалённым — мы нашли следующее разбиение, завершаем оба цикла и выполняем алгоритм дальше. Стоит отметить, что нельзя перезаписывать последний элемент в подмножестве, иначе мы не сможем дописать минимальный хвост после этого подмножества — в удалённых будет элемент меньше текущего и мы не сможем выписать удаленные элементы так, чтобы получилось корректное разбиение.
- Если заменить текущий элемент каким-то из удалённых нельзя, то следует удалить и этот.
- Допишем лексикографически минимальный хвост подмножеств из оставшихся удалённых элементов.
list<list<int>> nextSetPartition(list<list<int>> a):
used = list<int>
// a — список, содержащий подмножества
// used — список, в котором мы храним удаленные элементы
fl = false
for i = a.size - 1 downto 0
if (used.size != 0) and (max(used) > a[i][-1]) // в удалённых есть хотя бы один элемент, который мы можем добавить в конец.
m = минимум из used строго больше a[i][-1]
a[i].add(m) // добавляем
used.remove(m)
break
for j = a[i].size - 1 downto 0
if (used.size != 0) and (j != 0) and (max(used) > a[i][j]) // если можем заменить элемент, другим элементом из списка used и он не последний
m = минимум из used строго больше a[i][j]
old = a[i][j]
a[i][j] = m // заменяем
used.remove(m)
used.add(old)
fl = true
break
else
used.add(a[i][-1])
a[i].pop()
if a[i].size == 0
a.pop()
if fl
break
// далее выведем все удалённые, которые не выбрали
sort(used)
for i = 0 to used.size - 1
a.add(list<int>(used[i])) // добавляем лексикографически минимальных хвост
return a
Пример работы
Рассмотрим следующее разбиение:
| 1 | 2 | 3 |
| 4 | 5 |
1 Шаг:
| 1 | 2 | 3 | |
| 4 | 5 | ||
| ^ | Удалили элемент 5. | ||
| Удалённые элементы |
2 Шаг:
| 1 | 2 | 3 | |
| 4 | |||
| ^ | Удалили элемент 4. Так как он является последним в подмножестве, то мы не можем заменить его на другой. | ||
| 5 | Удалённые элементы |
3 Шаг:
| 1 | 2 | 3 | 4 | |
| ^ | Дополнили первое подмножество элементом 4 | |||
| 5 | Удалённые элементы |
4 Шаг:
| 1 | 2 | 3 | 4 | |
| 5 | Дописали лексикографически минимальный хвост | |||
| Удалённые элементы |
