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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Специализация алгоритма для генерации следующей перестановки)
Строка 14: Строка 14:
 
== Специализация алгоритма для генерации следующей перестановки ==
 
== Специализация алгоритма для генерации следующей перестановки ==
 
Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть.
 
Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть.
 
+
<code>
 
  bool Next(vector<int> &a) {
 
  bool Next(vector<int> &a) {
 
     int n = a.size();
 
     int n = a.size();
Строка 27: Строка 27:
 
      
 
      
 
     int l = j + 1, r = n - 1;
 
     int l = j + 1, r = n - 1;
     while (l < r) swap(a[l++],a[r--]);
+
     while (l < r) swap(a[l++], a[r--]);
 
     return true;
 
     return true;
 
  }
 
  }
 
+
</code>
 
=== Пример работы ===
 
=== Пример работы ===
  

Версия 09:15, 29 октября 2011

Алгоритм

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

Пусть дан объект [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])
  • Дописываем минимальный возможный хвост

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

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

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

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

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

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

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

Ссылки