Заведем массив B[0..n] из (n+1) элемента. B[i]=0, если i-ый
элемент в подмножество не входит, и B[i]=1 иначе. Т.о. пустому
подмножеству будет соответствовать набор из n нулей, а n-элементному
подмножеству - набор из n единиц. Тут явно заметна связь
подмножества с двоичным представлением числа.
Алгоритм: будем генерировать числа от 0 до 2n-1,
находить их двоичное представление, и формировать подмножество из
элементов с индексами единичных битов в этом представлении.
Но число 2n-1 может не поместиться в разрядную сетку
машины. Поэтому генерацию будем проводить, используя массив B:
Сначала B[i]=0 для всех i, что соответствует пустому
подмножеству.
Будем рассматривать массив B как запись двоичного числа
B[N]...B[1]B[0],
и моделировать операцию сложения этого числа с единицей. При
сложении будем просматривать число справа налево заменяя единичные
биты нулями до тех пор, пока не найдем нулевой бит, в который
занесем 1. Генерация подмножеств заканчивается, как только
B[N]=1
(предыдущая конфигурация была 1...12 =
2n-1).
while B[N]<>0 do begin i:=0; { индекс бита двоичного числа }
while (B[i]=1) do begin
B[i]:=0; { моделируем перенос в следующий разряд, }
i:=i+1 { возникающий при сложении }
end;
B[i]:=1;
{ Распечатываем индексы единичных элементов массива B
-новое сгенерированное подмножество }
For i:=0 to N-1 do
if B[i]=1 then write(i);
writeln; { переход на новую строку при печати }
Назад
