Идея такова: сохраняем все разбиения меньшей размерности и комбинируем их так, чтобы

1) они не повторялись;

2) количество элементов нового разбиения не было бы больше количества элементов n.

Итак, пусть мы имеем два начальных состояния: (*) и *. Для n=2 имеем только одно выходное понятие: (*)*. Для n=3 необходимо скомбинировать все известные ранее состояния с учётом условий 1)-2).

Условие 1) обеспечим из таких соображений: каждому элементу присвоить порядковый номер и комбинировать понятия так, чтобы порядковый номер следующего понятия не превосходил порядковый номер предыдущего понятия, а также следить, чтобы выполнялось условие 2). Отсюда видно, что повторений не будет, и мы перечислим все понятия.

Для реализации условия 2) необходимо каждому понятию присвоить число, которое будет показывать количество элементов этого состояния.

Также необходимо иметь некоторый массив, каждый элемент которого будет указывать на понятие, соответствующее номеру понятия в выходном понятии. Элементы этого массива будут меняться, в соответствии с перебором вариантов.

Язык программирования

Для реализации алгоритмов был выбран язык программирования TurboPascal 7.0. В этом языке есть все необходимые средства для этих алгоритмов, и сам язык является простым для понимания. Поэтому выбор пал именно на него.

Для алгоритмов нам понадобятся понятия указателей и записей.

Запись в Pascal’е описывается так:

<имя_типа>=|<имя_переменной>:record

<список полей и их типов>

end;

Например,

Var point:record

x,y: integer;

color:byte

end;

Обращаются к полям записи так:

Nx:=point.x+point.y;

Point . color :=3;

Указатели описываются так:

<имя_типа>=|<имя_переменной>:^< имя типа >

Например, k :^ integer – указатель на целое. Обращение к содержимому указателя: t := k ^ , а запись значения в ячейку памяти, куда указывает k, выглядит так: k ^:=10. Но, чтобі использовать указатели, необходимо сначала выделить память под них. Это делается с помощью команды new :

New ( k );

Чтобы освободить память, если указатель уже не будет нужен, используют

Dispose ( k );

Операторы присваивания, арифметических операций и циклов похожи во многих языках, поэтому их описывать не стоит.

Реализация алгоритмов

Генерирование разбиений множества

В табл.1 представлены разбиения для n=4, генерируемые следующим алгоритмом: