nextupprevious

Next:4.13 Порождение сочетаний
Up:4 Разработка алгоритмов
Previous:4.11 Порождение перестановок

4.12 Порождение подмножеств множества

Порождение всех подмножеств множества $\{ a_1,\ldots, a_n\}$ можно свести к порождению всех $n$-разрядных двоичных векторов (наборов), а именно: $a_i$ принадлежит подмножеству тогда и только тогда, когда $i$-й элемент вектора равен единице.

Известно, что наиболее простым способом порождения всех двоичных векторов $B= (b_n, b_{n-1},\ldots, b_1 )$ длины $n$ является счет в системе счисления с основанием 2, как это сделано в следующем алгоритме:
 

В качестве начального берется вектор из нулей $B=(0,0,\ldots,0)$;
while B # (1, 1, ..., 1) do
    Вывести текущее значение $B= (b_n, b_{n-1},\ldots, b_1 )$;
    Пусть $m$ -- наименьший номер нулевого элемента в $B$;
    Положить $b_m$ равным 1 и каждое $b_j, 1 \leq j < m$, равным нулю
end;
Вывести текущее значение $B$.
 

Понятно, что этот алгоритм не порождает подмножества в порядке минимального изменения, поскольку в порождаемой последовательности соседние наборы могут различаться во всех позициях. Например, соседними являются наборы $(0,1,1,1,\ldots,1)$ и $(1,0,0,0,\ldots,0)$.

Наименьшим возможным изменением при переходе от одного подмножества к другому является добавление или удаление одного элемента множества, что соответствует изменению только одного элемента в текущем двоичном векторе. Существуют и такие последовательности длиной $2^n$ всех $n$-разрядных двоичных наборов (кодовых слов), что последовательные кодовые слова различаются в одном разряде. Такие последовательности называются кодами Грея.

Рекурсивное определение $n$-разрядного кода Грея

$G(n)=(G(n)_0, G(n)_1, \ldots, G(n)_{2^n-1})$

можно сформулировать следующим образом:
 

$G(1)=(G(1)_0, G(1)_1)=(0,1),$$G(m+1)= (0G(m)_0,\ldots, 0G(m)_{2^m-1},$$1G(m)_{2^m-1},\ldots, 1G(m)_0)=$
= $(0G(m),1G(m)^R)$ для любого $m \geq 1,$

где $G(m)^R$ означает обращение двоичного слова $G(m)$ -- слово, получающееся выписыванием элементов слова $G(m)$ в обратной последовательности. Например, $G(4)=(0000,0001,0011,0010,0110,0111,0101,0100,$$1100,$$1101,$$1111,1110,1010, 1011,1001,1000)$.

Коды Грея $G(n)$ удобно представлять их последовательностью переходов $T_n$, т.е. упорядоченным списком номеров разрядов (пронумерованных справа налево), которые меняются при переходе от одного кодового слова к другому. Например, $T_4 =1,2,1,3,1,2,1,4,1,2,1,3,1,2,1$.

Для $T_n$ можно указать довольно простое рекурсивное определение:

$T_1=1$ и $T_{n+1}=T_n,n+1,T_n$ для любого $n\geq 1.$

Next:4.13 Порождение сочетаний
Up:4 Разработка алгоритмов
Previous:4.11 Порождение перестановок

© В.Н. Касьянов, Е.В.Касьянова,2004