Получение предыдущего объекта — различия между версиями
Flanir (обсуждение | вклад) (→Специализация алгоритма для генерации предыдущего разбиения на слагаемые) |
Flanir (обсуждение | вклад) (→Реализация) |
||
Строка 125: | Строка 125: | ||
=== Реализация === | === Реализация === | ||
− | Первое слагаемое находится под индексом 1. | + | Первое слагаемое находится под индексом <tex>1</tex>. |
'''list<int>''' prevPartition('''list<int>''' a): | '''list<int>''' prevPartition('''list<int>''' a): |
Версия 23:19, 30 декабря 2014
Содержание
Алгоритм
Определение: |
Получение предыдущего объекта — это нахождение объекта, предшествующего данному в лексикографическом порядке. |
Объект
называется предыдущим за , если и не найдется такого , что .Отсюда понятен алгоритм:
- находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта ,
- к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило ),
- дописываем максимально возможный хвост.
По построению получаем, что
— минимально возможный.Специализация алгоритма для генерации предыдущего битового вектора
- Находим минимальный суффикс, в котором есть , его можно уменьшить, не изменяя оставшейся части
- Вместо записываем
- Дописываем максимально возможный хвост из единиц
Реализация
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
Специализация алгоритма для генерации предыдущего разбиения на слагаемые
Рассматриваемый алгоритм находит предыдущее разбиение на слагаемые, при этом разбиение упорядочено по возрастанию.
Рассмотрим два случая:
Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на , так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.
Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое точно больше предыдущего на . Обозначим его номер за . Тогда , а . А будет последним слагаемым в разбиении.
Пример:
Случай 1.
Случай 2.
Реализация
Первое слагаемое находится под индексом
.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();