Генерация подмножеств в лексикографическом порядке.

Определение. Пусть A=(x₁,…,x_n) и B=(y₁,…,y_n), x_i,y_iÎ{0,1}, 1£i£n. Будем говорить, что множество А предшествует множеству B лексикографическом порядке ,если существует i, 1£i£n, x_i<y_i и x_j=y_j для любого j, 1£j<i; обозначим это А<B.

Упражнение. Пусть 0 £ a < b <2ⁿ, a, b - натуральные; представим a и b в двоичной системе с выписыванием всех n двоичных разрядов и пусть a = и b = . Доказать, что тогда (x₁,...,x_n) < (y₁,...,y_n).

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

program SET1(, output);

const n= ; n1= ; {n1=n+1}

var s : array [1..n1] of 0..1;

i,j : integer;

begin

for i:=1 to n1 do s[i]:=0;

while s[n1]=0 do

begin

for i:=1 to n do write(s[i]); writeln;

i:=1;

{**} while s[i]=1 do

begin s[i]:=0; i:=i+1 end;

{*} s[i]:=1

end

end.

Комментарий. Пусть множеству s соответствует число s, тогда множеству, следующему за s, соответствует число s+1.

Упражнения. 1.Доказать корректность алгоритма SET1.

2. Показать, что условие цикла {**} проверяется 2ⁿ⁺¹-1 раз.

3. Определить вычислительную сложность алгоритма.

4. Написать программу генерации всех подмножеств в лексикографическом порядке, если s описано как SET OF 1..n.

Замечания. 1.Следует отметить, что в системе команд любой вычислительной машины имеются команды, выполняющие арифметическое сложение двоичных последовательностей определенной длин, таких, как 8 бит - 1 байт, 16 - 2 байта и тому подобное. Кроме того, часто имеются специальные программные конструкции (например, макрокоманды, выполняющие сложение более длинных двоичных последовательностей). Непосредственное применение таких команд в программе SET1 может существенно улучшить ее временные характеристики.

2. Для построения других алгоритмов генерации подмножеств, представляет интерес свойства последовательности значений переменной i перед исполнением оператора {*}. Заметим, что этот оператор {*} исполняется 2ⁿ раз, при этом последнее значение i=n+1 приводит к окончанию генерации всех подмножеств для множества из n-элементов. Пусть I_n обозначает эту последовательность значений переменной i за исключением последнего. I_n можно трактовать как последовательность номеров позиций младшей единицы в двоичном разложении чисел 1, 2, ..., 2ⁿ-1. По построению двоичной позиционной системы последовательность I_n удовлетворяет следующему рекурсивному определению

I₁=1, I_n= I_n-1,n, I_n-1

(первый раз единица в n-ой позиции появляется для числа 2^n-1, при этом во всех других позициях с 1-ой по (n-1)-ую значения становятся нулевыми, затем для чисел 2^n-1+1,..., 2ⁿ-1 повторяется процесс заполнения единицами позиций с номерами меньшими n).

Упражнение. Доказать, что если I_n-1=i₁, i₂, ..., i, n>1, то I_n=1, i₁+1, 1, i₂+1, 1, ..., i+1, 1.