nextupprevious

Next:5 Выбор представления данных
Up:4 Разработка алгоритмов
Previous:4.12 Порождение подмножеств множества


4.13 Порождение сочетаний

Рассматривая порождение всех подмножеств множества $\{ a_1,\ldots, a_n\}$ фиксированной мощности $k$, т.е. всех сочетаний из $n$ предметов по $k$ штук, как обычно, будем предполагать, что основным множеством является подмножество натуральных чисел $ \{1,2,\ldots, n \}$.

Наиболее естественно рассматривать представление сочетания $\{a_{i_1},$$\ldots,$$ a_{i_k} \}$ в виде вектора $c=(c_1,\ldots, c_k)$, в котором компоненты сочетания расположены в порядке возрастания слева направо (т.е. $\{a_{i_1},$$\ldots,$$ a_{i_k} \}$= $\{c_1,\ldots, c_k\}$ и $c_i < c_{i+1}$ для любого $i$), и порождать эти векторы в лексикографическом порядке. Так, например, все 20 сочетаний из шести предметов по три (т.е. трехэлементные подмножества множества $\{ 1,2,3,4,5,6 \}$) образуют следующую лексикографически упорядоченную последовательность векторов: (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5), (1,3,6), (1,4,5), (1,4,6), (1,5,6), (2,3,4), (2,3,5), (2,3,6), (2,4,5), (2,4,6), (2,5,6), (3,4,5), (3,4,6), (3,5,6), (4,5,6).

Для порождения сочетаний (более точно, соответствующих векторов) в лексикографическом порядке можно воспользоваться следующим алгоритмом:

В качестве начального взять вектор C = (1, 2, ..., $k$);
while ~ (Для любого $i$ выполняется $c_i = n - k + i$) do
    Выдать текущее значение C;
    Найти такое максимальное $j$, что $c_j \ne n - k + j$;
    В качестве $c_j$ взять $c_j + 1$, а для всех $i$, начиная от $j+1$
    и кончая $k$, положить $c_i$ равным $c_{i-1}+1$
end;
Выдать текущее значение C.

Начинается порождение с сочетания $(1,2,\ldots, k)$. Каждое следующее сочетание строится из предыдущего с помощью следующих простых действий: в ходе просмотра текущего сочетания справа налево в нем находится самый первый элемент, который еще не достиг своего максимального значения; этот элемент увеличивается на единицу, а всем элементам справа от него последовательно приписываются новые наименьшие возможные значения.

Рассмотрим порождение сочетаний в порядке наименьшего изменения, т.е. таким образом, чтобы каждое последующее сочетание получалось из предыдущего заменой только одного элемента. Это означает, что последовательность двоичных слов, представляющих сочетания в этом порядке, состоит из так называемых $n-k-$слов ($n$-разрядных двоичных слов по $k$ единиц в каждом), и обладает тем свойством, что любые два соседних слова в последовательности различаются ровно в двух разрядах (позициях). Эту последовательность $n-k-$слов

$G(n,k) = (G(n,k)_1, G(n,k)_2, \ldots, G(n,k)_{C_n^k}),$

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

$G(n,0) = (G(n, 0)_1) = (0\ 0 ... 0),$
$G(n,n) = (G(n, n)_1) = (1\ 1 ... 1),$
$G(n,k) = (0G(n-1,k), 1G(n-1,k-1)^R)$ = $(0G(n-1,k)_1, \ldots, 0G(n-1,k)_{C_{n-1}^k},$
$1G(n-1, k-1)_{C_{n-1}^{k-1}},\ldots,$$1G(n-1, k-1)_1)$.

Индукцией по $n$ можно доказать, что такое определение $G(n,k)$ задает последовательность, которая получается удалением из кода Грея $G(n)$ всех кодовых слов с числом единиц, не равным $k$, и в ней любые два соседних кодовых слова различаются только в двух позициях.

Next:5 Выбор представления данных
Up:4 Разработка алгоритмов
Previous:4.12 Порождение подмножеств множества

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