Next:4.13
Порождение сочетаний
Up:4
Разработка алгоритмов
Previous:4.11
Порождение перестановок
Известно, что наиболее простым способом порождения всех двоичных векторов
длины
является счет в системе счисления с основанием 2, как это сделано в следующем
алгоритме:
В качестве начального берется вектор из нулей ;
while B # (1, 1, ..., 1) do
Вывести текущее значение ;
Пусть
-- наименьший номер нулевого элемента в
;
Положить
равным 1 и каждое
,
равным нулю
end;
Вывести текущее значение .
Понятно, что этот алгоритм не порождает подмножества в порядке минимального
изменения, поскольку в порождаемой последовательности соседние наборы могут
различаться во всех позициях. Например, соседними являются наборы
и
.
Наименьшим возможным изменением при переходе от одного подмножества
к другому является добавление или удаление одного элемента множества, что
соответствует изменению только одного элемента в текущем двоичном векторе.
Существуют и такие последовательности длиной
всех
-разрядных
двоичных наборов (кодовых слов), что последовательные кодовые слова различаются
в одном разряде. Такие последовательности называются кодами Грея.
Рекурсивное определение -разрядного
кода Грея
можно сформулировать следующим образом:
=
для любого
где
означает обращение двоичного слова
-- слово, получающееся выписыванием элементов слова
в обратной последовательности. Например,
.
Коды Грея
удобно представлять их последовательностью переходов
,
т.е. упорядоченным списком номеров разрядов (пронумерованных справа налево),
которые меняются при переходе от одного кодового слова к другому. Например,
.
Для
можно указать довольно простое рекурсивное определение:
и
для любого
Next:4.13
Порождение сочетаний
Up:4
Разработка алгоритмов
Previous:4.11
Порождение перестановок