Переборный поиск
Размещения с повторениями
Допустим, что в библиотеке есть $N$ книг по информатике и математическому моделированию, каждая в $m$ экземплярах. Сколькими способами можно выбрать $N$ книг из тех, что есть?
Каждому выбору соответствует строка длины $N$ над алфавитом мощности $m$. Это эквивалентно представлению числа от 0 до $m^N - 1$ в системе счисления по основанию $m$. Всего таких строк $m^N$.
Как перечислить все такие строки?
Способ 1: для каждого числа от 0 до $m^N - 1$ найдем его представление в $m$-ичной системе счисления.
Такой алгоритм имеет временную сложность $O(Nm^N)$.
Способ 2: работать непосредственно со строками цифр.
Пример: $m = 3$, $N = 2$. Строки: 00, 01, 02, 10, 11, 12, 20, 21, 22.
Пусть $A = 0..m-1$. Начнем со строки $(a_1, a_2, \ldots, a_N) = (0, 0, \ldots, 0) \in A^N$ и опишем алгоритм перехода к следующей строке в лексикографическом порядке.
\({\rm next}(@a \in A^N, i \in 1..N) = \{\)
$\qquad$ \(i \leftarrow 1\)
$\qquad$ \({\bf while}\;\; i \leq N \;\, \& \;\, a[i] = m-1 \;\; \{\)
$\qquad\qquad$ \(i \leftarrow i + 1\)
$\qquad$ \(\}\)
$\qquad$ // \(a[1..i-1] = m-1\)
$\qquad$ \({\bf if}\;\; i = N + 1 \;\; \{\)
$\qquad\qquad$ // $a[i] = m-1$ для всех $i$
$\qquad\qquad$ ${\bf return}\;\,{\rm NULL}$ // строки закончились
$\qquad$ \(\}\)
$\qquad$ \(a[i] \leftarrow a[i] + 1\)
$\qquad$ \({\bf for}\;\; j \leftarrow 1\,.\,.\,i-1 \;\; \{\)
$\qquad\qquad$ \(a[j] \leftarrow 0\)
$\qquad$ \(\}\)
\(\}\)
Тогда алгоритм перебора всех строк заключается в последовательном вызове функции next.
Оценим время работы алгоритма. Для этого оценим $S$ – сумму величин $f(a)$ по всем $a \in A^N$. Здесь $f(a)$ – это количество цифр $(m-1)$ в начале строки. Количество строк с $i$ цифрами $(m-1)$ в начале строки можно оценить сверху как $m^{N-i}$, поэтому \(S \leq \sum_{i=1}^N i m^{N-i} = O(Nm^N).\) Эта оценка сверху не является асимптотически точной, и ее можно улучшить до $O(m^N)$ [Федоряева, с. 48]. Действительно, $\sum_{i=1}^\infty im^{-i} < \infty$ [КЛРШ, с. 187].
Перестановки
Перестановкой множества $1..N$ называется взаимно однозначное отображение $\alpha \colon 1..N \to 1..N$.
Перестановка задается таблицей или вектором переставленных чисел. Например, при $N = 4$: $\alpha = (4, 1, 3, 2)$.
Количество перестановок длины $N$ равно $N! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (N-1) \cdot N$. Первый элемент перестановки можно выбрать $N$ способами, затем после выбора первого элемента останется $(N-1)$ вариантов выбора второго элемента перестановки, после выбора первых двух элементов выбрать третий можно будет $(N-2)$ способами и т.д. – всего получаем $N(N-1)(N-2)\cdot\ldots\cdot 2\cdot 1$ комбинаций.
Как перечислить все перестановки в лексикографическом порядке? Например, при $N = 3$: 123, 132, 213, 231, 312, 321.
Источники: [Федоряева, с. 27], презентация. В STL есть стандартная функция next_permutation для генерации перестановок в лексикографическом порядке.
Генерирование всех подмножеств
Требуется перечислить все подмножества множества $1..n$. Построим дерево рекурсии. На глубине $k$ находятся все возможные двоичные последовательности длины $k$. Тогда чтобы построить все возможные последовательности длины $k+1$, нужно провести к каждому узлу глубины $k$ два потомка: один левый и соответствует не включению элемента $k$ в подмножество (или цифре 0 в двоичном коде), другой правый соответствует цифре 1, когда элемент включается в подмножество. Двоичный код длины $n$ – это представление АТД “подмножество”. Генерацию всех возможных строк длины $n$ над алфавитом мощности 2 мы уже рассматривали выше. Сформулируем рекурсивный алгоритм.
// генерирует все возможные подмножества множества 1..i
void gen_subsets (int n, bool subset[], int i)
{
// subset[0..i-1] содержит двоичный код подмножества множества 1..i
if (i == n) {
// очередное подмножество множества 1..n найдено
print_subset(n, subset);
}
else {
subset[i] = false;
gen_subsets(n, subset, i + 1);
subset[i] = true;
gen_subsets(n, subset, i + 1);
}
}
Напомним, что данные, соответствующие входным параметрам рекурсивной процедуры, а также локальные переменные хранятся в стеке. При вызове рекурсивной процедуры на вершину стека помещаются новые параметры, и выполнение операторов процедуры начинается сначала, а после завершения выполнения процедуры из стека выталкиваются использованные данные, и управление передается тому месту, откуда была вызвана процедура. Таким образом, рекурсия подразумевает создание нескольких экземпляров рекурсивной процедуры, соответствующих разным входным параметрам.
В библиотеке GSL есть подпрограммы для генерации перестановок и сочетаний.
Литература
[Федоряева] Федоряева – Комбинаторные алгоритмы (2011)
[Скиена] Скиена – Алгоритмы. Руководство по разработке (2011) – С. 251-256
[КЛРШ] Кормен, Лейзерсон, Ривест, Штайн – Алгоритмы: Построение и анализ (2013)
[Ворожцов] Ворожцов, Винокуров – Алгоритмы: построение и анализ на Си (2007) – С. 211–215