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

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

Алгоритм

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

Объект [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, его можно увеличить, не меняя оставшейся части.
  • Вместо 0 записываем 1
  • Дописываем минимально возможный хвост из нулей

for i = n downto 1
    if a[i] == 0
        a[i] = 1
        for j = i + 1 to n
            a[j] = 0
        break

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

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 следующая перестановка

Ссылки