Получение следующего объекта — различия между версиями
Free0u (обсуждение | вклад) (→Пример работы) |
Korektur (обсуждение | вклад) (Добавлен раздел: "Специализация алгоритма для генерации следующего разбиения на подмножества") |
||
| Строка 61: | Строка 61: | ||
|'''1'''||'''3'''||'''4'''||'''2'''||'''5'''||следующая перестановка | |'''1'''||'''3'''||'''4'''||'''2'''||'''5'''||следующая перестановка | ||
|} | |} | ||
| + | |||
| + | == Специализация алгоритма для генерации следующего разбиения на подмножества == | ||
| + | * Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не выполнится одно из условий ниже: | ||
| + | |||
| + | 1) Каждый раз, рассматривая новый элемент, будем пытаться заменить его уже удаленным элементом из нашего массива, так чтобы не нарушалась возрастающая последовательность элементов в этом подмножестве. Из всех подходящих элементов выбираем минимальный. '''Важное замечание''': мы не можем заменить 1ый элемент подмножества, мы можем только удалить его. | ||
| + | |||
| + | 2) Каждый раз, переходя в новое подмножество, будем пытаться дополнить его элементом из уже удаленных, так чтобы не нарушалась возрастающая последовательность элементов этом подмножестве. Из всех подходящих элементов выбираем минимальный. | ||
| + | |||
| + | * Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов. | ||
| + | |||
| + | <code> | ||
| + | // a - матрица содержащая подмножества | ||
| + | // used - массив в котором мы храним, удаленные элементы | ||
| + | for i = n - 1 downto 0 //перебираем все подмножества, начиная с последнего | ||
| + | if ( /*можем добавить в конец подмножества элемент из used*/ ){ | ||
| + | // добавляем | ||
| + | break; | ||
| + | } | ||
| + | for j = m - 1 downto 0 // перебираем все элементы текущего подмножества | ||
| + | if( /* можем заменить элемент, другим элементом из массива used*/ ){ | ||
| + | //заменяем | ||
| + | break; | ||
| + | } | ||
| + | used.add(a[i][j]); //удаляем элемент и добавляем его в массив | ||
| + | printsets(); //далее выведем все получившиеся подмножества | ||
| + | sort(used); //отсортируем массив оставшихся элементов | ||
| + | for i = 0 to used.size() do | ||
| + | println(used[i]); //выведем лексикографически минимальный хвост | ||
| + | </code> | ||
| + | |||
| + | === Пример работы === | ||
| + | |||
| + | '''Рассмотрим следующее разбиение:''' | ||
| + | {1, 2, 3} | ||
| + | {4, 5} | ||
| + | |||
| + | '''1 Шаг:''' | ||
| + | {1, 2, 3} | ||
| + | {4} | ||
| + | used = {5}; | ||
| + | |||
| + | Удалили элемент 5. | ||
| + | |||
| + | '''2 Шаг:''' | ||
| + | {1, 2, 3} | ||
| + | used = {4, 5}; | ||
| + | |||
| + | Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой. | ||
| + | |||
| + | '''3 Шаг:''' | ||
| + | {1, 2, 3, 4} | ||
| + | {5} | ||
| + | used = {}; | ||
| + | |||
| + | Дополнили первое подмножество элементом 4(так как он минимальный из всех элементов, которыми мы могли его дополнить), и дописали лексикографически минимальный хвост. | ||
== Ссылки == | == Ссылки == | ||
Версия 20:54, 19 декабря 2012
Содержание
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта
- К оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть 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 | следующий битовый вектор |
Специализация алгоритма для генерации следующей перестановки
- Двигаясь справа налево, находим элаемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
- Меняем его с минимальным элементом, большим нашего, стоящим правее
- Перевернем правую часть
for i = n - 1 downto 1
if a[i] < a[i + 1]
// a[j] = min {a[j] > a[i], где j > i}
swap(a[i], a[j])
reverse(a[i + 1] .. a[n])
break
Пример работы
| 1 | 3 | 2 | 5 | 4 | исходная перестановка |
| ^ | находим элемент, нарушающий убывающую последовательность | ||||
| ^ | минимальный элемент больше нашего | ||||
| 1 | 3 | 4 | 5 | 2 | меняем их местами |
| 1 | 3 | 4 | 2 | 5 | разворачивам правую часть |
| 1 | 3 | 4 | 2 | 5 | следующая перестановка |
Специализация алгоритма для генерации следующего разбиения на подмножества
- Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не выполнится одно из условий ниже:
1) Каждый раз, рассматривая новый элемент, будем пытаться заменить его уже удаленным элементом из нашего массива, так чтобы не нарушалась возрастающая последовательность элементов в этом подмножестве. Из всех подходящих элементов выбираем минимальный. Важное замечание: мы не можем заменить 1ый элемент подмножества, мы можем только удалить его.
2) Каждый раз, переходя в новое подмножество, будем пытаться дополнить его элементом из уже удаленных, так чтобы не нарушалась возрастающая последовательность элементов этом подмножестве. Из всех подходящих элементов выбираем минимальный.
- Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.
// a - матрица содержащая подмножества
// used - массив в котором мы храним, удаленные элементы
for i = n - 1 downto 0 //перебираем все подмножества, начиная с последнего
if ( /*можем добавить в конец подмножества элемент из used*/ ){
// добавляем
break;
}
for j = m - 1 downto 0 // перебираем все элементы текущего подмножества
if( /* можем заменить элемент, другим элементом из массива used*/ ){
//заменяем
break;
}
used.add(a[i][j]); //удаляем элемент и добавляем его в массив
printsets(); //далее выведем все получившиеся подмножества
sort(used); //отсортируем массив оставшихся элементов
for i = 0 to used.size() do
println(used[i]); //выведем лексикографически минимальный хвост
Пример работы
Рассмотрим следующее разбиение: {1, 2, 3} {4, 5}
1 Шаг: {1, 2, 3} {4} used = {5};
Удалили элемент 5.
2 Шаг: {1, 2, 3} used = {4, 5};
Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой.
3 Шаг: {1, 2, 3, 4} {5} used = {};
Дополнили первое подмножество элементом 4(так как он минимальный из всех элементов, которыми мы могли его дополнить), и дописали лексикографически минимальный хвост.
