Подмножества множества

Порождение подмножеств множества (a1,a2,…,an) эквивалентно порождению n - разрядных двоичных наборов: ai принадлежит подмножеству, если и только если i-й разряд равен единице. Таким образом, задача порождения всех подмножеств множества сводится к задаче порождения всех возможных двоичных последовательностей длины n.

Следующий алгоритм описывает эту процедуру:

Листинг 6.4 Алгоритм генерации подмножеств множества. for i=0 to n do bi ←0;

while bn≠1 do begin

вывести (bn-1bn-2…b0); i←0;

while bi=1 do begin

bi ←0;

i ← i+1;

end;

bi ← 1;

end.

25