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

Алгоритм

Определение:

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

Объект [math]Q[/math] называется следующим за [math]P[/math], если [math]P \lt Q[/math] и не найдется такого [math]R[/math], что [math]P \lt R \lt Q[/math].

Отсюда понятен алгоритм:

• Находим минимальный суффикс в объекте [math]P[/math], который можно увеличить, не меняя префикс
• К префиксу дописываем минимальный возможный элемент (чтобы было выполнено правило [math]P \lt Q[/math])
• Дописываем минимальный возможный хвост

По построению получаем, что [math]Q[/math] — минимально возможный.

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

Двигаемся справа налево по элементам объекта, пока не найдем элемент 0. Заменим его на 1, а все элементы справа на нули.

bool next_vec(vector<int> &a) {
    int n = a.size();
    int pos = n - 1;
     
    while (pos != -1 && a[pos] == 1) --pos;
    if (pos == -1) return false;

    a[pos] = 1;
    while (++pos < n) a[pos] = 0;
    return true;
}

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

0	1	0	1	1	исходный битовый вектор
		^			находим элемент 0 (самый правый)
0	1	1	1	1	меняем его на 1
0	1	1	0	0	меняем элементы правее на нули
0	1	1	0	0	следующий битовый вектор

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

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

bool next_permutation(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[pos], a[k]);
   
    int l = pos + 1, r = n - 1;
    while (l < r) swap(a[l++], a[r--]);
    return true;
}

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

1	3	2	5	4	исходная перестановка
		^			находим элемент, нарушающий убывающую последовательность
				^	минимальный элемент больше нашего
1	3	4	5	2	меняем их местами
1	3	4	2	5	разворачивам правую часть
1	3	4	2	5	следующая перестановка

Ссылки

• Визуализатор перестановок
• Пример компактного кода для перестановок