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

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

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

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

  • .
  • .
  • .
  • .
  • .
  • .

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

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

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

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

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

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

Реализация на 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);
}

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

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

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

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

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

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

Сочетания

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

  • .
  • .
  • .
  • .
  • .
  • .

Число возможных сочетаний из по обозначается и вычисляется по формуле

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

Наивный

Используется в случаях, когда нужно посчитать небольшое количество за каждое. Реализация на 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.

ДП

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

Таким образом мы можем рассчитать значения для всех и за .

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

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...
}