Получение следующего объекта — различия между версиями
Free0u (обсуждение | вклад) (→Алгоритм) |
Free0u (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
* К префиксу дописываем минимальный возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>) | * К префиксу дописываем минимальный возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>) | ||
* Дописываем минимальный возможный хвост | * Дописываем минимальный возможный хвост | ||
| + | |||
| + | == Специализация алгоритма для генерации следующего битового вектора == | ||
| + | === Пример работы === | ||
== Специализация алгоритма для генерации следующей перестановки == | == Специализация алгоритма для генерации следующей перестановки == | ||
| Строка 28: | Строка 31: | ||
} | } | ||
| − | == Пример работы == | + | === Пример работы === |
{| border="1" | {| border="1" | ||
Версия 09:06, 29 октября 2011
Содержание
Алгоритм
| Определение: |
| Получение следующего объекта - это нахождение объекта, следующего за данным в лексикографическом порядке. |
Пусть дан объект . Назовем объект следующим, если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим минимальный суффикс в объекте , который можно увеличить, не меняя префикс
- К префиксу дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
Специализация алгоритма для генерации следующего битового вектора
Пример работы
Специализация алгоритма для генерации следующей перестановки
Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть.
bool Next(vector<int> &a) {
int n = a.size();
int pos = n - 2;
while (pos != -1 && a[pos] > a[pos + 1]) --pos;
if (pos == -1) return false;
int k = n - 1;
while (a[pos] > a[k]) --k;
swap(a[j], a[k]);
int l = j + 1, r = n - 1;
while (l < r) swap(a[l++],a[r--]);
return true;
}
Пример работы
| 1 | 3 | 2 | 5 | 4 | исходная перестановка |
| ^ | находим элемент, нарушающий убывающую последовательность | ||||
| ^ | минимальный элемент больше нашего | ||||
| 1 | 3 | 4 | 5 | 2 | меняем их местами |
| 2 | 5 | разворачивам правую часть | |||
| 1 | 3 | 4 | 2 | 5 | следующая перестановка |
