Генерация следующего объекта: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(статья по генерации следующего объекта)
 
м (как получить предыдущий)
 
Строка 23: Строка 23:
  
 
По сути критерий того, что суффикс можно увеличить заключается в том, что он не является суффиксом последовательности $1, 2, 3, \dots, N - 1, N$
 
По сути критерий того, что суффикс можно увеличить заключается в том, что он не является суффиксом последовательности $1, 2, 3, \dots, N - 1, N$
 +
 +
===Как получить предыдущий===
 +
Здесь наоборот надо найти минимальный суффикс, который можно уменьшить. Как правильно изменить найденный суффикс - первый элемент в суффиксе изменяем на предыдущий возможный, а остальной суффикс делаем максимальным из всех возможных.
 +
 +
Рассмотрим пример для перестановок из восьми элементов:
 +
 +
$(1, 5, 2, 3, 6, 4, 7, 8) \Rightarrow (1, 5, 2, 3, [6, 4, 7, 8]) \Rightarrow (1, 5, 2, 3, 4, 8, 7, 6)$
 +
 +
{{Автор|Полина Романченко|Romanchenko}}
 +
[[Категория:Комбинаторика]]
 +
[[Категория:Конспект]]

Текущая версия на 19:44, 5 апреля 2020

Решим следующую задачу - пусть дана перестановка/сочетание/размещение, надо по ней сгенерировать следующий в лексикографическом порядке объект.

Например, перестановки из 8 элементов:

$(1, 5, 2, 3, 4, 8, 7, 6) \Rightarrow (1, 5, 2, 3, 6, 4, 7, 8)$

Общий принцип вне зависимости от типа объекта такой - надо найти минимальный по длине суффикс, который можно увеличить (лексикографически), не трогая при этом остальной префикс.

Перестановки

Что это значит для перестановок? Посмотрим на тот же пример. Будем постепенно увеличивать суффикс и проверять, можно ли его увеличить.

  • $(1, 5, 2, 3, 4, 8, 7, [6])$ Одну шестерку никак не изменить
  • $(1, 5, 2, 3, 4, 8, [7, 6])$ Суффикс - (7,6) из семерки и шестерки нельзя собрать ничего большего
  • $(1, 5, 2, 3, 4, [8, 7, 6])$ Суффикс - (8,7,6), тут тоже элементы образуют максимальную возможную перестановку между собой.
  • $(1, 5, 2, 3, [4, 8, 7, 6])$ Вот теперь суффиксом будет $(4, 8, 7, 6)$, мы можем его увеличить. Для этого на первую позицию в суффиксе поставим следующее за четверкой число, в данно случае это 6, а потом оставшиеся числа расставим так, чтобы конец получился наименьшим возможным. То есть ставим шестерку на первое место, а оставшиеся числа расставим по возрастанию.

Сочетания

Сохраняем тот же принцип, каждое сочетание представляет собой отсортированную последовательность чисел от $1$ до $N$ длины $K$. Значит, будем искать такой суффикс, в котором можно увеличить первый элемент за счет чисел, не использованных в префиксе. Оставшийся суффикс будет логично дополнить последовательными числами, они точно не использовались в префиксе, так как последовательность всегда отсортирована.

Рассмотрим пример: $C_6^4$

$(1, 2, 5, 6)$

Ни суффикс $(6)$, ни $(5,6)$ увеличить нельзя, можем взять только $(2, 5, 6)$. Значит, заменим $2$ на $3$, а дальше дополним последовательными числами - $(3, 4, 5)$.

По сути критерий того, что суффикс можно увеличить заключается в том, что он не является суффиксом последовательности $1, 2, 3, \dots, N - 1, N$

Как получить предыдущий

Здесь наоборот надо найти минимальный суффикс, который можно уменьшить. Как правильно изменить найденный суффикс - первый элемент в суффиксе изменяем на предыдущий возможный, а остальной суффикс делаем максимальным из всех возможных.

Рассмотрим пример для перестановок из восьми элементов:

$(1, 5, 2, 3, 6, 4, 7, 8) \Rightarrow (1, 5, 2, 3, [6, 4, 7, 8]) \Rightarrow (1, 5, 2, 3, 4, 8, 7, 6)$



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko