Получение следующего объекта

Материал из Викиконспекты
Перейти к: навигация, поиск

Алгоритм

Определение:
Получение следующего объекта - это нахождение объекта, следующего за данным в лексикографическом порядке.


Специализация алгоритма для генерации следующей перестановки

Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть.

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;
}

Пример работы

Ссылки