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

Материал из Викиконспекты
Версия от 09:31, 29 октября 2011; Free0u (обсуждение | вклад) (Специализация алгоритма для генерации следующей перестановки)
Перейти к: навигация, поиск

Алгоритм

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

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

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

  • Находим минимальный суффикс в объекте [math]P[/math], который можно увеличить, не меняя префикс
  • К префиксу дописываем минимальный возможный элемент (чтобы было выполнено правило [math]P \lt 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;
    for (int i = pos + 1; i < n; ++i) a[i] = 0;
    return true;
}

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

0 1 0 1 1 исходный битовый вектор
^ находим элемент 0 (самый правый)
1 1 1 меняем его на 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 исходная перестановка
^ находим элемент, нарушающий убывающую последовательность
^ минимальный элемент больше нашего
4 5 2 меняем их местами
2 5 разворачивам правую часть
1 3 4 2 5 следующая перестановка

Ссылки