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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Специализация алгоритма для генерации следующего битового вектора)
Строка 11: Строка 11:
  
 
== Специализация алгоритма для генерации следующего битового вектора ==
 
== Специализация алгоритма для генерации следующего битового вектора ==
Двигаемся справа налево по элементам объекта, пока не найдем элемент 0. Заменим его на 1, а все элементы справа на нули.
+
* Находим минимальный суффикс, в котором есть 0, его можно увеличить, не меняя оставшейся части.
 +
* Вместо 0 записываем 1
 +
* Дописываем минимально возможный хвост из нулей
 
<code>
 
<code>
  bool next_vec(vector<int> &a) {
+
  for i = n to 1
    int n = a.size();
+
  if a[i] == 0
    int pos = n - 1;
+
     a[i] = 1
     
+
     for j = i + 1 to n
    while (pos != -1 && a[pos] == 1) --pos;
+
      a[j] = 0
    if (pos == -1) return false;
+
     break
 
     a[pos] = 1;
 
     while (++pos < n) a[pos] = 0;
 
     return true;
 
}
 
 
</code>
 
</code>
 
=== Пример работы ===
 
=== Пример работы ===

Версия 09:45, 20 декабря 2011

Алгоритм

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

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

Ссылки