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

Множество всех подмножеств множества X обозначается P{X}. Каждое N-элементное множество X={x₁, x₂, …, x_n} имеет в точности 2ⁿ подмножеств. Это можно показать следующим образом.

Сопоставим элементам множества

X={x₁, x₂, …, x_n}

бинарную последовательность

b_1, b_2,…, b_n

определяемую следующим образом.

Пусть задано подмножество YX. Тогда:

b_i = 0 если x_i  Y

b_i = 1 если x_i  Y.

Тем самым устанавливается взаимно однозначное соответствие между элементами множества всех подмножеств P{X} и всеми бинарными последовательностями длины N.

Установленная описанным выше способом последовательность

b₁, b₂, …, b_n

становится хорошим способом машинного представления любого подмножества Y, особенно когда мощность множества X не велика и последовательность

b₁, b₂, …, b_n

может быть представлена с помощью одного машинного слова. В современных персональных компьютерах это 32 или 64 разряда, что для большинства практических задач вполне достаточно.

Предложенное представление множества приводит к простому способу генерирования всех подмножеств. Действительно, каждая бинарная последовательность

b_n-1, b_n-2, …, b₀

соответствует числу r из интервала 0 r 2ⁿ-1. В результате достаточно последовательно получать все числа из интервала 0 r 2ⁿ-1, а их двоичные представления дадут все подмножества N‑элементного множества.

При таком способе получения очередного подмножества два соседних подмножества могут значительно отличаться друг от друга. Например, после (n-1) элементного множества, соответствующего двоичному числу

0111…1

следует одноэлементное множество, соответствующее числу

1000…0

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

5.1Генерация всех подмножеств множества

Можно предложить следующий простой способ получения подмножеств, отличающихся друг от друга одним элементом. Пусть получены все m=2^k бинарные последовательности длины k. Обозначим их через:

C₁, C₂, …, C_m-1, C_m

Причем C_i отличается от C_i+1 в точности в одной позиции бинарной последовательности. Тогда все бинарные последовательности длины k+1 могут быть получены приписыванием справ от каждой последовательности элементов 0 или 1. То есть получим

C₁0, C₂0, …, C_m-10, C_m0, C_m1, C_m-11, …, C₂1, C₁1

Этот алгоритм имеет рекуррентный характер, так как предполагает получение всех комбинаций сначала для k=1, затем для k=2 и т.д.

Ниже приводится не рекуррентный алгоритм генерации всех подмножеств исходного множества. Идею алгоритма можно вывести из следующего примера. Пусть длина исходной последовательности B равна 4. Обозначим через i десятичный номер генерируемой последовательности. Представим очередность получения последовательностей в следующем виде:

i = 0 0 0 0 0

i = 1 1 0 0 0

i = 2 1 1 0 0

i = 3 0 1 0 0

i = 4 0 1 1 0

i = 5 1 1 1 0

i = 6 1 0 1 0

i = 7 0 0 1 0

i = 8 0 0 1 1

i = 9 1 0 1 1

i = 10 1 1 1 1

i = 11 0 1 1 1

i = 12 0 1 0 1

i = 13 1 1 0 1

i = 14 1 0 0 1

i = 15 0 0 0 1

Можно заметить следующие закономерности:

• В случае перехода к последовательности с нечетным номером (i ‑нечетно) в первой позиции (p=1) последовательности B происходит смена значения на противоположное.

• В случае перехода к последовательности с четным номером (I ‑ четно) позиция p последовательности, в которой значение B[p] меняется на противоположное определяется следующим образом. Номер позиции p удовлетворяет условию: 2^p-1 является наибольшей степенью числа 2, на которое делится число i. Ниже для четных значений номера последовательности i приведены соответствующие значения позиции p.

I	p
2	2
4	3
6	2
8	4
10	2
12	3
14	2

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

program AllSubSets;

{Генерирует все подмножества N - элементного множества. Каждое подмножество представляется бинарной последовательностью B[1], B[2], ..., B[N]. Каждое последующее подмножество получается из предыдущего, добавлением или удалением единственного элемента.}

uses Crt;

const N = 4;

var B: array [1..N] of integer;

procedure SubSet;

var I: integer; {Номер очередной последовательности, подлежащей генерации}

P: integer; ^{Позиция элемента в массиве В, значение которого будет меняться с 0 на 1 или наоборот с 1 на 0}

J, K: integer;

begin

{Массив B обрабатывается (заполняется) слева направо путем смены значений отдельных его элементов с 0 на 1 и, наоборот, с 1 на 0}

for K := 1 to N do B [K] := 0; {Пустое множество}

I := 0; {Число сгенерированных до этого момента подмножеств}

repeat

Write (' ');

for K := 1 to N do Write (' ', B[K]);

Writeln;

I := I + 1; {Номер следующей последовательности, подлежащей генерации}

P := 1; {Начальное значение позиции Р для предстоящей генерации}

J := I;

while J mod 2 = 0 do

{Определяется Р - реальная позиция элемента массива, значение которого подлежит смене. Если I нечетно, то Р = 1. Если I четно, то после завершения всех итераций J - нечетно, а Р - степень числа 2, для которой выполняется J*2^P-1 = I. Т.е. Р-1 это наибольшая степень числа 2, которая делит I нацело. Например, при I = 6 получим J = 3 и P-1 = 1}

begin

J := J div 2;

P := P + 1;

end;

if P <= N then B[P] := 1 - B[P]; {смена позиции P}

until P > N;

end;

begin

Clrscr;

SubSet;

end.