Тема 3. Генерация подмножеств множества

При программировании на языке Паскаль возможны два подхода к представлению подмножеств конечного множества. В первом, основанном на использовании структурного типа SET OF, базовый тип (элементы множества) задается некоторым простым типом. При этом пользователь может давать имена элементам множества, определять их упорядоченность и применять операции, допустимые над множествами языка Паскаль. Второй подход основан на том, что пользователь интерпретирует множества с помощью других типов, чаще всего массивов. В этом случае, элементы множества трактуются как элементы массива, они могут считаться как упорядоченные, например, по упорядоченности индекса, а выполняемые над ними операции определяются применяемыми операторами или процедурами. Возможна также интерпретация множеств в виде списочных структур. Отметим, что второй подход естественен, когда по условию программируемой задачи элементы сами по себе имеют сложную структуру.

Следует отметить, что описания множеств с использованием типа SET OF фактически сводится к представлению множеств в виде упакованных булевских массивов и реализация соответствующих операций над ними. Но для удобства пользователя все это выполняется в процессе трансляции программы.

Для того чтобы более точно описать проблемы, возникающие в нижеописанных алгоритмах, будем считать, что базовое множество содержит n элементов, а каждое конкретное его подмножество представляется в виде массива. При этом i-й элемент массива принимает значение 1, если i-й базовый элемент (1 £ i £ n) принадлежит множеству, и нулю в противном случае (сравните с понятием характеристической функции множества, используемое в математике). Кроме того, считаем, что упорядоченность элементов множества соответствует упорядоченности индексов массива. Будем изображать множества в виде кортежей из n нулей и единиц.

Пример. X=(1,0,0,0,1,1) означает, что базовое множество содержит шесть упорядоченных элементов, а в множество X включены первый, пятый и шестой по порядку элементы. Пустое множество в этом случае представляется (0,0,0,0,0,0), а множество всех элементов (1,1,1,1,1,1).

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