Получение предыдущего объекта
Алгоритм
| Определение: |
| Получение предыдущего объекта — это нахождение объекта, предшествующего данному в лексикографическом порядке. |
Объект называется предыдущим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта ,
- к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило ),
- дописываем максимально возможный хвост.
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации предыдущего битового вектора
- Находим минимальный суффикс, в котором есть , его можно уменьшить, не изменяя оставшейся части
- Вместо записываем
- Дописываем максимально возможный хвост из единиц
Пример:
Реализация
int[] prevVector(int[] a): // — длина вектора
while (n >= 0) and (a[n] != 1)
a[n] = 1
n--
if n == -1
return null
a[n] = 0
return a
Приведённый алгоритм эквивалентен вычитанию единицы из битового вектора.
Специализация алгоритма для генерации предыдущей перестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
- Меняем его с максимальным элементом, меньшим нашего, стоящим правее
- Перевернем правую часть
Пример:
Реализация
int[] prevPermutation(int[] a): // — длина перестановки
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
Мультиперестановка
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.
Специализация алгоритма для генерации предыдущего сочетания
- Проходя справа налево, находим элемент так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом равен , а первый элемент хранится в )
- уменьшаем его на единицу
- дописываем максимально возможный хвост
Если элемента не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.
Пусть массив хранит сочетания так, что первый элемент хранится в
Пример:
Реализация
int[] prevChoose(int[] a): // — количество различных элементов a[0] = 0 // — длина сочетания 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
Специализация алгоритма для генерации предыдущего разбиения на слагаемые
Рассматриваемый алгоритм находит предыдущее разбиение на слагаемые, при этом разбиение упорядочено по возрастанию.
Рассмотрим два случая:
Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на , так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.
Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое точно больше предыдущего на . Обозначим его номер за . Тогда , а . А будет последним слагаемым в разбиении.
Пример:
Первый случай:
Второй случай:
Реализация
Первое слагаемое находится под индексом .
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();
Специализация алгоритма для генерации предыдущего разбиения на множества
Рассматриваемый алгоритм находит предыдущее разбиение на множества.
Пусть нам надо получить разбиение некого множества непомеченных элементов, например, разложить одинаковые шары по коробкам. Пусть множества упорядочены по убыванию мощностей, а разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .
Пример упорядоченного списка разбиений множества из элементов:
Рассмотрим алгоритм нахождения лексикографически предыдущего разбиения на подмножества:
- Будем хранить подмножества в списке , например, разбиение будет выглядеть так:
| 3 | 1 | 1 | 1 |
Будем идти справа налево и применять следующий алгоритм:
- Найдём множество минимальной мощности , которое можно разбить на два множества, мощности которых равны и соответственно
- Если — первый элемент, то мы не можем добавить единицу никуда правее, следовательно предыдущее разбиение должно состоять из множеств, мощности которых
- Иначе исключим элемент из —ого множества и добавим его к множеству(при условии что мощность множества не станет больше , иначе создадим множество из элемента)
Реализация
list<int> PreviousSetPartition(list<int> a)
for int i = a.size - 1 downto 0 // найдем минимальный элемент, от которого можно отнять 1
if a[i] > 1
a[i] --
if i > 0 // см 2 пункт алгоритма
if i + 1 < a.size // если справа есть еще элементы
a[i + 1] ++
else a.push_back(1)
else int sum = 1 // пройдемся до конца массива и найдем сумму оставшихся элементов
for j = i + 1 to a.size
sum += a[j]
while a[a.size] != a[0] // удалим все элементы кроме 1, чтобы заполнить теми, что не превышают a[0]
a.pop_back
while sum > a[0]
sum -= a[0]
a.push(a[0])
if sum != 0
a.push(sum);
break // break нужен для того, чтобы мы остановились после первого подходящего элемента
return a
Пример работы
Рассмотрим следующее разбиение:
| 3 | 1 |
1 Шаг:
| 3 | 1 | |
| ^ | 3 — наименьший элемент, от которого мы можем отнять 1, однако 3 также является первым элементом, значит предыдущее разбиение должно состоять из элементов . |
2 Шаг:
| 2 | 1 | |
| ^ | уменьшили 3 на 1, прошли до конца списка, вычислили сумму оставшихся элементов, которую теперь надо распределить на элементы | |
| 1 | 1 | sum |
3 Шаг:
| 2 | ||
| ^ | удалили все элементы кроме первого |
4 Шаг:
| 2 | 2 | |
| ^ | распределили сумму |
