kz-maxx

RU KZ
← Главная

Сочетания

Выбор k элементов из n, формула C(n,k), генерация и подсчет

Что такое сочетание?

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

выбрать k элементов из n
порядок не учитывается

Например, если есть числа: 

1 2 3

Сочетания по 2: 

1 2
1 3
2 3

Здесь 1 2 и 2 1 — это одно и то же сочетание.

Обозначение

Количество сочетаний обозначают так: 

C(n, k)

Или так: 

n choose k

Это читается:

сколько способов выбрать k элементов из n

Формула сочетаний

Формула: 

C(n, k) = n! / (k! * (n - k)!)

Например: 

C(5, 2) = 5! / (2! * 3!)

Считаем: 

5! = 120
2! = 2
3! = 6

C(5, 2) = 120 / (2 * 6) = 10

Почему порядок не важен?

Допустим, выбираем 2 человека из 3: 

A B C

Сочетания: 

A B
A C
B C

Пары A B и B A считаются одинаковыми.

Если порядок важен, это уже не сочетания, а размещения или перестановки.

Сочетания, размещения, перестановки

Тип Что значит Порядок важен?
Сочетания Выбрать k из n Нет
Размещения Выбрать k из n и расставить Да
Перестановки Расставить все n элементов Да

Пример разницы

Есть: 

1 2 3

Сочетания по 2: 

1 2
1 3
2 3

Размещения по 2: 

1 2
2 1
1 3
3 1
2 3
3 2
В сочетаниях порядок не важен, поэтому вариантов меньше.

Свойства C(n,k)

Главные свойства: 

C(n, 0) = 1
C(n, n) = 1
C(n, k) = C(n, n - k)

Почему C(n, 0) = 1? Потому что есть ровно один способ выбрать ничего.

Почему C(n, n) = 1? Потому что есть ровно один способ выбрать все элементы.

Формула Паскаля

Очень важная формула: 

C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

Смысл:

берем последний элемент
или не берем последний элемент
  • C(n - 1, k - 1) — последний элемент взяли
  • C(n - 1, k) — последний элемент не взяли

Треугольник Паскаля

Значения C(n,k) можно представить как треугольник: 

n = 0:        1
n = 1:       1 1
n = 2:      1 2 1
n = 3:     1 3 3 1
n = 4:    1 4 6 4 1
n = 5:   1 5 10 10 5 1

Например: 

C(5, 2) = 10

Подсчет C(n,k) через DP

Можно считать через формулу Паскаля: 

C[n][k] = C[n - 1][k - 1] + C[n - 1][k]

База: 

C[i][0] = 1;
C[i][i] = 1;

Код: C(n,k) через DP

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

long long C[N + 1][N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int n = 0; n <= N; n++) {
        C[n][0] = 1;
        C[n][n] = 1;

        for (int k = 1; k < n; k++) {
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
        }
    }

    int n, k;
    cin >> n >> k;

    cout << C[n][k];

    return 0;
}
Такой код подходит только для небольших n, потому что значения C(n,k) быстро становятся огромными.

Подсчет по модулю

В задачах часто нужно считать: 

C(n, k) mod MOD

Тогда в DP просто берем остаток после сложения. 

C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;

Код: C(n,k) через DP по модулю

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
const long long MOD = 1000000007;

long long C[N + 1][N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int n = 0; n <= N; n++) {
        C[n][0] = 1;
        C[n][n] = 1;

        for (int k = 1; k < n; k++) {
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
        }
    }

    int n, k;
    cin >> n >> k;

    cout << C[n][k];

    return 0;
}

C(n,k) через факториалы

Если n большой и много запросов, удобно заранее посчитать факториалы: 

fact[i] = i!

Тогда: 

C(n, k) = fact[n] / (fact[k] * fact[n-k])

По модулю деление заменяется на обратный элемент.

Быстрая степень

Для обратного элемента по простому модулю используем: 

inv(x) = x^(MOD - 2) mod MOD

Поэтому нужна быстрая степень: 

long long binpow(long long a, long long b) {
    long long res = 1;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

Код: C(n,k) через factorial

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;
const long long MOD = 1000000007;

long long fact[N + 1];
long long invFact[N + 1];

long long binpow(long long a, long long b) {
    long long res = 1;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long x) {
    return binpow(x, MOD - 2);
}

void build() {
    fact[0] = 1;

    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invFact[N] = inv(fact[N]);

    for (int i = N - 1; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long comb(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }

    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build();

    int n, k;
    cin >> n >> k;

    cout << comb(n, k);

    return 0;
}

Генерация сочетаний

Иногда нужно не количество, а вывести все сочетания.

Например, для: 

n = 4
k = 2

Нужно вывести: 

1 2
1 3
1 4
2 3
2 4
3 4

Идея генерации

Будем строить ответ рекурсивно. На каждом шаге выбираем следующее число.

cur — текущее сочетание
start — с какого числа можно брать следующий элемент
если cur.size() == k, выводим cur

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

Код: генерация сочетаний

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> cur;

void gen(int start) {
    if ((int)cur.size() == k) {
        for (int x : cur) {
            cout << x << ' ';
        }

        cout << '\n';
        return;
    }

    for (int x = start; x <= n; x++) {
        cur.push_back(x);
        gen(x + 1);
        cur.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    gen(1);

    return 0;
}

Пример генерации

Input

4 2

Output

1 2
1 3
1 4
2 3
2 4
3 4

Оптимизация генерации

Можно не перебирать лишние числа. Если осталось мало чисел, нет смысла продолжать.

Осталось выбрать: 

need = k - cur.size()

Значит последнее возможное первое число: 

n - need + 1

Код: оптимизированная генерация

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> cur;

void gen(int start) {
    if ((int)cur.size() == k) {
        for (int x : cur) {
            cout << x << ' ';
        }

        cout << '\n';
        return;
    }

    int need = k - (int)cur.size();

    for (int x = start; x <= n - need + 1; x++) {
        cur.push_back(x);
        gen(x + 1);
        cur.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    gen(1);

    return 0;
}

Генерация через битмаски

Если n маленькое, можно перебрать все маски от 0 до 2^n - 1.

В маске бит равен 1, если элемент выбран.

mask = 10110
выбраны элементы, где стоят единицы

Для сочетания размера k нужно, чтобы количество единиц было равно k.

Код: сочетания через битмаски

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) == k) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    cout << i + 1 << ' ';
                }
            }

            cout << '\n';
        }
    }

    return 0;
}
Этот способ работает только для маленьких n, потому что всего масок 2^n.

next_permutation для сочетаний

Можно создать массив из нулей и единиц. Единица означает, что элемент выбран.

Например, для n = 5, k = 3: 

0 0 1 1 1

Потом запускаем next_permutation.

Код: сочетания через next_permutation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> a(n, 0);

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

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

        cout << '\n';
    } while (next_permutation(a.begin(), a.end()));

    return 0;
}

Когда какой способ использовать?

Задача Способ
Нужно количество C(n,k), n маленькое DP Паскаля
Нужно количество C(n,k), n большое Факториалы + inverse
Нужно вывести все сочетания Рекурсия / backtracking
n маленькое и удобно работать с подмножествами Битмаски
Нужен простой способ через STL next_permutation

Асимптотика

Метод Время Память
DP Паскаля O(n²) O(n²)
Факториалы build O(n log MOD) O(n)
Один запрос C(n,k) после build O(1) O(n)
Генерация всех сочетаний O(C(n,k) * k) O(k)
Битмаски O(2^n * n) O(1)

Типичные ошибки

  • Путать сочетания и перестановки
  • Считать 1 2 и 2 1 разными сочетаниями
  • Забыть базы C(n,0)=1 и C(n,n)=1
  • Получить overflow при обычном подсчете C(n,k)
  • Использовать факториалы без модуля для больших n
  • Делить по модулю обычным делением
  • В генерации не делать pop_back()
  • В генерации начинать всегда с 1 и получить повторы

Короткий шаблон генерации

int n, k;
vector<int> cur;

void gen(int start) {
    if ((int)cur.size() == k) {
        for (int x : cur) {
            cout << x << ' ';
        }

        cout << '\n';
        return;
    }

    for (int x = start; x <= n; x++) {
        cur.push_back(x);
        gen(x + 1);
        cur.pop_back();
    }
}

Короткий шаблон C(n,k) mod

long long comb(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }

    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

Главное запомнить

сочетание = выбрать k из n
порядок не важен
C(n,k) = n! / (k! * (n-k)!)
C(n,k) = C(n-1,k-1) + C(n-1,k)
все сочетания удобно генерировать рекурсией