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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 14: Строка 14:
 
      
 
      
 
     int k = n - 1;
 
     int k = n - 1;
     while (a[pos] > a[k]) k--;
+
     while (a[pos] > a[k]) --k;
 
     swap(a[j], a[k]);
 
     swap(a[j], a[k]);
 
      
 
      

Версия 11:37, 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;
}

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

Ссылки