91
правка
Изменения
Добавлен раздел: "Специализация алгоритма для генерации следующего разбиения на подмножества"
|'''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(так как он минимальный из всех элементов, которыми мы могли его дополнить), и дописали лексикографически минимальный хвост.
== Ссылки ==
