Получение следующего объекта — различия между версиями
Free0u (обсуждение | вклад) м (→Пример работы) |
Free0u (обсуждение | вклад) (→Пример работы) |
||
| Строка 25: | Строка 25: | ||
{| border="1" | {| border="1" | ||
| − | + | |1||3||2||5||4||исходная перестановка | |
| − | + | |- | |
| − | + | | || ||^|| || ||находим элемент, нарушающий убывающую последовательность | |
| − | + | |- | |
| − | + | | || || || ||^||минимальный элемент больше нашего | |
| − | + | |- | |
| − | + | |1||3||4||5||2||меняем их местами | |
| + | |- | ||
| + | | || || ||2||5||разворачивам правую часть | ||
| + | |- | ||
| + | |1||3||4||2||5||следующая перестановка | ||
|} | |} | ||
== Ссылки == | == Ссылки == | ||
Версия 23:38, 28 октября 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 | следующая перестановка |
