2.5. Генерация комбинаторных объектов

Существует набор задач, решение которых заключается в генерации всех элементов таких комбинаторных объектов, как множество всех подмножеств, перестановки, сочетания, размещения, перестановки с повторениями, сочетания с повторениями. Для каждого сгенерированного элемента проверяются какие-то свойства для конкретной задачи.

ПРИМЕЧАНИЕ В дальнейшем предлагается следующий порядок изложения материала для каждого комбинаторного объекта: пример, алгоритм, программа, комментарии к программе. Все программы для большей наглядности оперируют с массивом символов от A до Z. Очевидно, что предлагаемые алгоритмы и программы практически не изменяются при работе с массивами элементов любого типа, требуемого по условиям задачи (например, массивами чисел, слов, геометрических фигур и т. д.).

Множество всех подмножеств

Пусть мы имеем множество из четырех компонент, которые обозначаем латинскими буквами A, B, C, D. И пусть, по условиям задачи, требуется выбрать подмножество, состоящее из нескольких компонент, обладающее некоторым свойством. Предлагается такой способ решения задачи: мы генерируем все возможные подмножества данного множества и для каждого из сгенерированных подмножеств проверяем, удовлетворяет ли оно заданному свойству. Альтернативный вариант задачи - подсчитать все подмножества данного множества, обладающие заданным свойством. Например: для множества из четырех символов A, B, C, D множество всех подмножеств включает в себя следующие множества: пустое множество;

• одноэлементные множества: {A}, {B}, {C}, {D};

• двухэлементные множества: {A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D};

• трехэлементные множества: {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D};

• четырехэлементное множество: {A, B, C, D}.

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

может принимать значение 0 или 1. И будем считать, что значение 1 указывает на включение соответствующего по номеру компонента исходного множества в искомое. Значение 0 указывает на то, что элемент не включается. Рассмотрим теперь последовательность двоичных чисел от 0 до 15 и соответствующие им подмножества:

1. {0000} - пустое множество;

2. {0001} - A, {0010} - B, {0100} - C, {1000} - D;

{0011} - AB, {0101} - AC, {0110} - BC, {1001} - AD, {1010} - BD, {1100} –

3. CD;

4. {0111} - ABC, {1011} - ABD, {1101} - ACD, {1110} - BCD;

5. {1111} - ABCD.

Таким образом, всего имеется 16 различных подмножеств множества из 4 элементов. В общем случае множество всех подмножеств множества из N элементов содержит 2^N элементов. Алгоритм, обеспечивающий генерацию множества всех подмножеств из N элементов, может быть неформально описан следующим образом: формируем массив, соcтоящий из N нулей, и рассматриваем его как пустое множество. Таким образом, начальное значение текущего подмножества - пустое множество. Для получения следующего подмножества из текущего подмножества обрабатываем текущий массив из чисел 0 или 1 следующим образом: справа (от первого элемента массива к последнему) ищем первое число, равное 0. Если такое число не найдено, то текущее подмножество является последним, то есть множеством, состоящим из всех элементов. На этом алгоритм заканчивает свою работу. Если же элемент, равный 0, найден, то он заменяется на 1, а все числа справа от него (если таковые имеются) заменяются на нули. Более формализованно этот алгоритм может быть записан следующим образом:   Ввод (N)   Обнуление массива B из N+1 элемента   Вывод (Пустое множество)   Пока B[N+1]=0     i=1     Пока B[i]=1 делать B[i]=0, i=i+1     B[i]=1     Вывод (множества, определяемого массивом B) Теперь легко написать текст программы, которая считывает число элементов во множестве (N) и выводит на экран множество всех подмножеств, обозначая элементы соответствующими по порядку латинскими буквами (листинг 2.38). Листинг 2.38. Программа генерации множества всех подмножеств const   alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var   b : array [1..100] of byte;   N,i : byte; begin   readln(N);   for i:=1 to N+1 do b[i]:=0;   writeln ('Пустое множество');   while (b[N+1]=0) do     begin

      i:=1;       while B[i]=1 do

        begin B[i]:=0; inc(i); end;       B[i]:=1;       for i:=1 to n do         if b[i]=1 then write(alphabet[i]);       writeln;     end; end.

ПРИМЕЧАНИЕ При необходимости обрабатывать (анализировать) построенные подмножества можно добавить вызовы процедур обработки, получающие в качестве параметра массив B, указывающий своими единичными элементами номера элементов множества, включенных в текущее подмножество.