Получение следующего объекта — различия между версиями
Free0u (обсуждение | вклад) (→Специализация алгоритма для генерации следующего битового вектора) |
Free0u (обсуждение | вклад) (→Специализация алгоритма для генерации следующей перестановки) |
||
| Строка 37: | Строка 37: | ||
== Специализация алгоритма для генерации следующей перестановки == | == Специализация алгоритма для генерации следующей перестановки == | ||
Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть. | Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть. | ||
| + | * Двигаясь справа налево, находим элаемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример) | ||
| + | * Меняем его с минимальным элементом, большим нашего, стоящим правее | ||
| + | * Перевернем правую часть | ||
<code> | <code> | ||
| − | + | 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 | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</code> | </code> | ||
=== Пример работы === | === Пример работы === | ||
Версия 10:03, 20 декабря 2011
Содержание
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим минимальный суффикс в объекте , который можно увеличить, не меняя оставшуюся часть
- К оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть 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 | следующая перестановка |
