Комбинаторика

Комбинаторика, как можно судить по названию, - раздел математики, изучающий различные комбинации объектов и множеств. Комбинаторика очень тесно связана с информатикой, и часто встречается в олимпиадных задачах. Она включает в себя множество понятий, но в программировании чаще всего используются две из них:

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

Когда две последовательности состоят из одинаковых объектов, расположенных в разном порядке, они называются перестановками одной и той же последовательности. Например, для последовательности \(1, 2, 3\) существует 6 перестановок:

  • \(1, 2, 3\).
  • \(1, 3, 2\).
  • \(2, 1, 3\).
  • \(2, 3, 1\).
  • \(3, 1, 2\).
  • \(3, 2, 1\).

Рассчитать число существующих перестановок достаточно просто. На первое место может стать один из \(N\) элементов. На второе место - один из \(N - 1\) оставшихся. На третье \(N - 2\), и так далее. На последнее место может стать только один элемент, нигде до этого не использовавшийся. Значит, количество перестановок последовательности длиной \(N\) равно

\[P_N = 1 * 2 * \ldots * N = \prod\limits_{i = 1}^N i = N!\]

Факториал, по определению, и является количеством перестановок последовательности длиной \(N\).

Более интересная алгоритмически задача: вывести все перестановки заданной последовательности. Наивный алгоритм её решения является достаточно эффективным, и является отличным примером распространённого подхода рекурсивного перебора.

Суть алгоритма проста. Обозначим изначальную последовательность \(a\). Определим рекурсивную функцию \(f(i_1, i_2, \ldots, i_k)\). Вызов этой функции должен вывести все перестановки последовательности \(a\), начинающиеся с чисел \(a[i_1], a[i_2], \ldots, a[i_k]\).

Крайний случай рекурсии очевиден: если \(k = N\), то \(a[i_1], a[i_2], \ldots, a[i_k]\) и есть одна из перестановок. Просто выведем её. Во всех других случаях поступаем следующим образом: пусть \(j_1, j_2, \ldots, j_{N - k}\) - ещё не использованные индексы. По очереди рекурсивно вызовем \(f(i_1, i_2, \ldots, i_k, j_1)\), \(f(i_1, i_2, \ldots, i_k, j_2)\), \(\ldots\), \(f(i_1, i_2, \ldots, i_k, j_{N - k})\). Таким образом мы гарантированно переберём все возможные перестановки.

На практике передача в функцию такого большого числа аргументов - плохая идея, поэтому функция реализуется по-другому. Просто будем поддерживать глобальный вектор \(v\), в который по мере углубления рекурсии будем добавлять элементы текущей перестановки. Кроме него также будем поддерживать глобальный массив \(used\): если при вызове функции f для какого-либо \(i\) выполняется условие \(used[i]\), это значит, что индекс \(i\) уже был использован.

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>

using namespace std;

int n;
int a[100000];

bool used[100000];
vector<int> v;

void f(int k) {     //k - количество уже использованных индексов
    if (k == n) {
        cout << "Permutation: ";
        for (int i: v) {
            cout << i << ", ";
        }
        cout << endl;

        return;
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;     //Добавляем в текущую перестановку элемент a[i]
            v.push_back(i);
            f(k + 1);           //Рекурсивно перебираем все перестановки, продолжающиеся a[i]
            v.pop_back();
            used[i] = false;    //Убираем из текущей перестановки элемент a[i]
        }
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }

    f(0);
}

Сложность этого алгоритма порядка \(O(N! * N^2)\), он будет укладываться в ограничение по времени при \(N \le 10\).

Стоит отметить, что этот алгоритм выводит перестановки в лексикографическом порядке. Так же, как расположены слова в словаре.

Приём рекурсивного перебора, использующийся в этом алгоритме, очень часто может добавить вам 15-20 баллов по задаче, по которой иначе вы бы получили 0 (речь идёт о белорусской системе оценки, где каждый тест оценивается индивидуально). Внимательно изучите его и поэкспериментируйте с ним.

Впрочем стандартная библиотека C++ содержит функции, позволяющие вам перебирать перестановки последовательности в лексикографическом порядке без написания своего кода:

//Преобразует перестановку в следующую лексикографически
//Если перестановка уже является максимальной, возвращает false
bool next_permutation(iterator begin, iterator end);

//Преобразует перестановку в предыдущую лексикографически
//Если перестановка уже является минимальной, возвращает false
bool prev_permutation(iterator begin, iterator end);

Сочетания

Сочетанием из \(n\) по \(k\) называется любой набор из \(n\) элементов, выбранных из данных \(k\) элементов. Например, рассмотрим множество \(1, 2, 3, 4\). Существует 6 сочетаний по 2 из этого множества:

  • \(1, 2\).
  • \(1, 3\).
  • \(1, 4\).
  • \(2, 3\).
  • \(2, 4\).
  • \(3, 4\).

Число возможных сочетаний из \(n\) по \(k\) обозначается \(C_n^k\) и вычисляется по формуле

\[C_n^k = {n! \over k! * (n - k)!}\]

Число сочетаний очень часто встречается в задачах по программированию. Существуют два способа его вычисления:

Наивный

Используется в случаях, когда нужно посчитать небольшое количество \(C_n^k\) за \(O(N)\) каждое. Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
long long fact(int x) {
    long long result = 1;
    for (int i = 2; i <= x; i++) {
        result *= i;
    }

    return result;
}

long long combinations(int n, int k) {
    return fact(n) / fact(k) / fact(n - k);
}

Разумеется, область применения такого подхода сильно ограничена вместимостью типа long long.

ДП

Выразим \(C_n^k\) рекурсивно. Рассмотрим последний (\(n\)-ый) элемент: все сочетания можно разделить на две группы: те которые включают его, и те которые не включают. Заметим, что все сочетания первой группы содержат \(k - 1\) элементов из первых \(n - 1\), а все сочетания второй группы: \(k\) из первых \(n - 1\). Значит,

\[C_n^k = C_{n - 1}^k + C_{n - 1}^{k - 1}\]

Таким образом мы можем рассчитать значения \(C_n^k\) для всех \(n \le N\) и \(k \le K\) за \(O(NK)\).

Реализация на С++ (значения в поле по модулю \(10^9 + 7\)):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1e9 + 7;

long long c[1001][1001];

int main() {
    c[1][1] = 1;
    for (int n = 2; n <= 1000; n++) {
        c[n][1] = n;
        for (int k = 2; k <= n; k++) {
            c[n][k] = (c[n - 1][k] + c[n - 1][k - 1]) % MOD;
        }
    }

    //Можем использовать c...
}