3622
правки
Изменения
Нет описания правки
Упорядочим все разбиения на множества <tex>N_n</tex> лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество <tex> A \subset N_n </tex> лексикографически меньше подмножества <tex> B \subset N_n </tex> , если верно одно из следующих условий:
*существует <tex>i</tex> такое, что <tex>i \in A</tex> , <tex>i \notin AB</tex>, для всех <tex>j < i: j \in A</tex> если и только если <tex>j \in B</tex> , и существует <tex>k > i</tex> такое что <tex>k \in B</tex>;
* <tex> A \subset B </tex> и <tex>i < j</tex> для всех <tex>i \in A</tex> и <tex>j \in B</tex> \ <tex> A </tex>.
|}
* Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не выполнится сможем выполнить одно из условий действий, описанных ниже:** Мы можем заменить Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. '''Важное замечание''': мы не можем заменить 1ый элемент подмножества, мы можем только удалить его.** Мы можем дополнить Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
* Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.
<code>
// a - матрица содержащая подмножестваn подмножеств
// used - массив в котором мы храним, удаленные элементы
'''for''' i = n '''downto''' 0
'''if''' можем добавить в конец подмножества элемент из used
'''if''' можем заменить элемент, другим элементом из массива used
//далее выведем все получившиеся подмножества
