Сгенерировать все подмножества данного n-элементного множества (0, .., n-1)

Материал из DRKB


Заведем массив 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; { переход на новую строку при печати }


Source: http://algolist.manual.ru
ID: 04183