91
правка
Изменения
Нет описания правки
== Специализация алгоритма для генерации следующего разбиения на подмножества ==
{{Определение
|id=def1.
|definition='''Разбиением на множества''' называется представление множества, как объединения одного или более, попарно
непересекающихся подмножеств множеств.
}}
Например для n = 5 существуют следующие разбиения:
'''{1, 2, 3, 4, 5}'''
'''{1, 2, 3} {4, 5}'''
'''{1, 3, 5} {2, 4}'''
'''{1} {2} {3} {4} {5}'''
и т. д., всего таких разбиений для n = 5 существует 52.
'''Примечание:'''
{1, 2, 3} {4, 5} и {4, 5} {1, 2, 3} - одно и то же разбиение на подмножества.
Упорядочим все разбиения на множества Nn лексикографически. Для этого во-первых в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество <tex> A \subset N_n </tex> лексикографически меньше подмножества <tex> B \subset N_n </tex> , если верно одно из следующих условий:
*существует i такое, что <tex>i \in A</tex> , <tex>i \notin A</tex>, для всех j < i: <tex>j \in A</tex> если и только если <tex>j \in B</tex> , и существует k > i такое что <tex>k \in B</tex>;
* <tex> A \subset B </tex> и i < j для всех <tex>i \in A</tex> и <tex>j \in B</tex> \ <tex> A </tex>.
Разбиения упорядочены лексикографически следующим образом. Разбиение <tex>N_n = A_1 \cup A_2 \cup . . . \cup A_k</tex> лексикографически меньше разбиения <tex>N_n = B_1 \cup B_2 \cup . . . \cup B_l</tex> если существует такое <tex>i</tex>, что <tex>A_1 = B_1, A_2 = B_2, . . . ,A_{i - 1} = B_{i - 1}, A_i < B_i</tex>.
'''Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:'''
*Будем хранить подмножества с помощью двумерного массива, например, разбиение {1, 2, 3} {4, 5} будет выглядеть так:
{| class="wikitable" border = 1
|1||2||3
|-
|4||5||
|}
* Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не выполнится одно из условий ниже:
** Каждый раз, рассматривая новый элемент, будем пытаться заменить его уже удаленным элементом из нашего массива, так, чтобы не нарушалась возрастающая последовательность элементов в этом подмножестве. Из всех подходящих элементов выбираем минимальный. '''Важное замечание''': мы не можем заменить 1ый элемент подмножества, мы можем только удалить его.
// a - матрица содержащая подмножества
// used - массив в котором мы храним, удаленные элементы
for i = n - 1 downto 0 //перебираем все подмножества, начиная с последнего if ( /*можем добавить в конец подмножества элемент из used*/ ){
// добавляем
break;
//заменяем
break;
=== Пример работы ===
'''Рассмотрим следующее разбиение:'''
{| class="wikitable" border = 1|1, ||2, ||3}{|-|4, ||5|| |}
'''1 Шаг:'''
{| class="wikitable" border = 1|1||2||3|||-|4||style="background:#FFCC00"|5|||||-| ||^|| ||Удалили элемент 5. |-| || || ||used|}
'''2 Шаг:'''
{| class="wikitable" border = 1|1||2||3|||-|style="background:#FFCC00"|4|| |||||-|^|| || ||Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой.|-|5|| || ||used|}
'''3 Шаг:'''
{| class="wikitable" border = 1|1||2||3||style="background:#FFCC00"|4|||-| || || ||^||Дополнили первое подмножество элементом 4(так как он минимальный из всех элементов, которыми мы могли его дополнить), и дописали лексикографически минимальный хвост.|-|5|| || || ||used|}
'''4 Шаг:'''
{| class="wikitable" border = 1
|1||2||3||4||
|-
|style="background:#FFCC00"|5|| || || ||Дописали лексикографически минимальный хвост
|-
| || || || ||used
|}
== Ссылки ==
* [[Получение объекта по номеру]]
