Получение следующего объекта — различия между версиями
Free0u (обсуждение | вклад) (→Специализация алгоритма для генерации следующего битового вектора) |
Free0u (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
</code> | </code> | ||
=== Пример работы === | === Пример работы === | ||
| − | + | {| border="1" | |
| + | |0||1||0||1||1||исходный битовый вектор | ||
| + | |- | ||
| + | | || ||^|| || ||находим элемент 0 (самый правый) | ||
| + | |- | ||
| + | | || ||1||1||1||меняем его на 1 | ||
| + | |- | ||
| + | | || ||1||0||0||меняем элементы правее на нули | ||
| + | |- | ||
| + | |0||1||1||0||0||следующий битовый вектор | ||
| + | |} | ||
== Специализация алгоритма для генерации следующей перестановки == | == Специализация алгоритма для генерации следующей перестановки == | ||
Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть. | Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть. | ||
<code> | <code> | ||
| − | bool | + | bool next_permutation(vector<int> &a) { |
int n = a.size(); | int n = a.size(); | ||
int pos = n - 2; | int pos = n - 2; | ||
| Строка 46: | Строка 56: | ||
</code> | </code> | ||
=== Пример работы === | === Пример работы === | ||
| − | |||
{| border="1" | {| border="1" | ||
|1||3||2||5||4||исходная перестановка | |1||3||2||5||4||исходная перестановка | ||
| Строка 54: | Строка 63: | ||
| || || || ||^||минимальный элемент больше нашего | | || || || ||^||минимальный элемент больше нашего | ||
|- | |- | ||
| − | | | + | | || ||4||5||2||меняем их местами |
|- | |- | ||
| || || ||2||5||разворачивам правую часть | | || || ||2||5||разворачивам правую часть | ||
Версия 09:25, 29 октября 2011
Содержание
Алгоритм
| Определение: |
| Получение следующего объекта - это нахождение объекта, следующего за данным в лексикографическом порядке. |
Пусть дан объект . Назовем объект следующим, если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим минимальный суффикс в объекте , который можно увеличить, не меняя префикс
- К префиксу дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
Специализация алгоритма для генерации следующего битового вектора
Двигаемся справа налево по элементам объекта, пока не найдем элемент 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[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 | исходная перестановка |
| ^ | находим элемент, нарушающий убывающую последовательность | ||||
| ^ | минимальный элемент больше нашего | ||||
| 4 | 5 | 2 | меняем их местами | ||
| 2 | 5 | разворачивам правую часть | |||
| 1 | 3 | 4 | 2 | 5 | следующая перестановка |
