На главную   ::   Содержание



Алгоритмы генерации подмножеств, перестановок и других комбинаторных объектов

Подмножества.

Задано множество $ X$ из $ n$ элементов. Для простоты положим, что $ X=\{1,2,\ldots,n\}$. Требуется указать все его подмножества.

Будем считать, что множество $ X$ упорядочено в том смысле, что порядок элементов в нем задан раз и навсегда и не меняется, то есть каждый элемент в множестве имеет уникальный номер от $ 1$ до $ n$. Составим характеристический вектор $ \chi$ (из $ n$ элементов) из нулей и единиц. $ \chi_i=1$ означает, что элемент с множества $ X$ с номером $ i$ выбирается в качестве элемента подмножества. $ \chi_i=0$ означает, что элемент с номером $ i$ не входит в подмножество. Любое подмножество $ Y\subset X$ однозначно задается своим характеристическим вектором. Поэтому задача генерации всех подмножеств эквивалентна задаче генерации всех векторов из нулей и единиц с $ n$ элементами.

Очевидно, что для существует $ 2^n$ векторов длины $ n$ из нулей и единиц. Генерация таких векторов -- то же самое, что генерация двоичных чисел на отрезке $ [0,2^n-1]$. Простейший алгоритм такой генерации следующий. Пусть сначала вектор $ \chi=(0,\ldots,0)$ -- пустое множество. На каждом шаге алгоритма справа налево ищется первый нулевой элемент. При этом во время поиска все пройденные единицы меняются на нули. Найденный ноль меняется на единицу. Полученный вектор и есть хар. вектор очередного подмножества. Например, на некотором шаге был вектор:

$\displaystyle \chi=(0,0,1,0,1,1);
$

нашли первый ноль справа

$\displaystyle \chi=(0,0,1,\mathbf 0,1,1);
$

поменяли его на единицу, а все единицы справа -- на нули:

$\displaystyle \chi=(0,0,1,\mathbf 1,\mathbf 0, \mathbf 0);
$

это и есть вектор для следующего подмножества.

Процесс остановится, когда мы получим $ \chi=(1,\ldots,1)$ -- что соответствует числу $ 2^n-1$ -- все множество целиком.

На псевдоязыке приведем программу:

24pt SUBSETS()

24pt
1
$ n\leftarrow \vert X\vert$

2
$ \chi\leftarrow \mathbb{O}_{n+1}$
3
while $ \chi_{n+1}=0$ do
4
for $ i\in 1..n$ do if $ \chi_i=1$ then write($ X_i$)
5
writeln
6
$ i\leftarrow 1$
7
while $ \chi_i=1$ do $ \chi_i\leftarrow 0$, $ i\leftarrow i+1$
8
$ \chi_i\leftarrow 1$

Перестановки.

Определение 1.   Перестановка (на множестве из $ n$ элементов) -- биективное отображение множества $ \{1,2,\ldots,n\}$ в себя.

Пример обозначения перестановки:

$\displaystyle \begin{pmatrix}
1 & 2 & \ldots & n \\
a_1 & a_2 & \ldots & a_n \\
\end{pmatrix}
$

Пример перестановки: $ (5,1,4,2,3)$.

Легко доказать (например, по индукции), что для упорядоченного множества из $ n$ элементов существует $ n!$ перестановок. Классический алгоритм генерации всех перестановок из $ n$ элементов позволяет получить эти перестановки в лексикографическом порядке. Алгоритм начинает с $ (1,2,\ldots,n)$ и заканчивает на $ (n,n-1,\ldots,1)$. Опишем его работу на примере. Пусть на некотором шаге получилась перестановка

$\displaystyle (6,5,4,2,7,3,1).
$

Для того чтобы определить непосредственно следующую за ней перестановку, необходимо, пересматривая данную перестановку справа налево, следить за тем, чтобы каждое следующее число было больше предыдущего, и остановиться сразу же, как только это правило нарушится. Место останова указано стрелкой:

$\displaystyle (6,5,4,\mathbf{\stackrel{\downarrow}{2}},7,3,1).
$

Затем вновь просматриваем пройденный путь (справа налево) до тех пор, пока не дойдем до первого числа, которое уже больше отмеченного. Ниже место второго останова отмечено двойной стрелкой.

$\displaystyle (6,5,4,\mathbf{\stackrel{\downarrow}{2}},7,\mathbf{\stackrel{\Downarrow}{3}},1).
$

Поменяем местами отмеченные числа:

$\displaystyle (6,5,4,\mathbf{\stackrel{\Downarrow}{3}},7,\mathbf 2,1).
$

Теперь в зоне, расположенной справа от двойной стрелки, упорядочим все числа в порядке возрастания. Так как до сих пор они были упорядочены по убыванию (так будет всегда), то это легко сделать, перевернув указанный отрезок. Получим:

$\displaystyle (6,5,4,3,1,2,7).
$

Это и есть та перестановка, которая получается следующей в лексикографическом порядке. Примем это утверждение без доказательства.

На псевдоязыке приведем программу:

24pt TRANSPOS

24pt
1
$ X\leftarrow (1,2,\ldots,n)$
2
while true do
3
for $ i\in 1..n$ do white($ X_i$)
4
writeln
5
$ i\leftarrow n-1$
6
while $ i>0$ and $ X_i>X_{i+1}$ do $ i\leftarrow i-1$
7
if $ i=0$ then break
8
$ j\leftarrow n$
9
while $ X_i>X_j$ do $ j\leftarrow j-1$
10
поменять $ X_i\leftrightarrow X_j$
11
$ i\leftarrow i+1$, $ j\leftarrow n$
12
while $ i<j$ do
13
поменять $ X_i\leftrightarrow X_j$
14
$ i\leftarrow i+1$, $ j\leftarrow j-1$

Сочетания.

Определение 2.   Сочетанием из $ n$ элементов по $ k$ называется любой неупорядоченный набор из $ k$ различных элементов, выбранных из генеральной совокупности в $ n$ элементов.

Пример: есть множество $ \{1,2,3\}$. Можно выбрать тремя способами два элемента: $ \{1,2\}$, $ \{1,3\}$ и $ \{2,3\}$. Всего число способов выбрать $ n$ из $ k$ есть

$\displaystyle C_n^k=\frac{n!}{k!(n-k)!}
$

Пусть дан массив $ X=(1,2,\ldots,n)$ и мы хотим выписать все его подмножества, содержащие $ k$ элементов. Это можно сделать, например, генерируя все подмножетва и выбирая из них только те, в которорых $ k$ элементов, но это гораздо дольше, чем если использовать классический алгоритм.

Опишем его. В массиве $ A$ будут находиться индексы используемых на данном шаге элементов из $ X$ (общее их число $ k$). В качестве начальной конфигурации возьмем следующую: $ A_j=j$, $ j=\overline{1,k}$. Ищем $ A_j$ с максимальным индексом $ j$ такое, что

$\displaystyle A_j<n+j-k,
$

увеличиваем $ A_j$ на $ 1$, а для всех $ i>j$ полагаем $ A_i=A_{i-1}+1$ ($ A_j$ растут с ростом $ j$, и мы ищем и увеличиваем на $ 1$ такое $ A_j$ с максимальным номером $ j$, чтобы при заполнении возрастающими значениями элементов массива $ A_i:  i>j$, последний элемент $ A_k$ не превосходил бы $ n$). Если такого $ A_j$ не существует, то генерация сочетаний для данного $ k$ закончена.

На псевдоязыке приведем программу:

24pt COMB

24pt
1
$ A\leftarrow (1,2,\ldots,k)$
2
while true do
3
for $ i\in 1..k$ do white($ A_i$)
4
writeln
5
$ j\leftarrow k$
6
while $ j>0$ and $ A_j\geqslant n+j-k$ do $ j\leftarrow j-1$
7
if $ j=0$ then break
8
$ A_j\leftarrow A_j+1$
9
for $ i\in [j+1,k]$ do $ A_i\leftarrow A_{i-1}+1$



На главную   ::   Содержание