Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

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

---

Формула

$\Huge{C(n, k) = \frac{{n!}}{{k! \cdot (n - k)!}}}$

• $C(n,k)$ - количество сочетаний без повторений из $n$ элементов, выбранных $k$ элементов.
• $n!$ - факториал числа n, что означает произведение всех положительных целых чисел от $1$ до $n$.
• $k!$ - факториал числа $k$.
• $(n−k)!$- факториал разницы между $n$ и $k$.

Принцип работы

У нас есть набор {A, B, C, D}, и мы хотим выбрать 2 элемента из этого набора без учёта порядка.

Определение переменных:

• $n$ — общее количество элементов, из которых мы выбираем. Здесь: $n=4$, так как у нас есть 4 элемента: A, B, C, D.
• $k$ — количество элементов, которые мы выбираем из общего числа nn. В этом примере: $k=2$, так как нам нужно выбрать 2 элемента из 4, но порядок не важен.

Разберем все по шагам:

• Шаг 1: Подсчёт количества сочетаний без повторений Число сочетаний из $n$ по $k$ без повторений рассчитывается по формуле: $C(n, k) = \frac{{n!}}{{k! \cdot (n - k)!}}$

• Шаг 2: Подстановка значений Подставим значения $n=4$ и $k=2$ в формулу: $C(4, 2) = \frac{{4!}}{{2! \cdot (4 - 2)!}} = 6$

• Шаг 3: Проверка результата (перечисление сочетаний) Все возможные пары, где порядок не имеет значения: AB, AC, AD, BC, BD, CD.

Всего 6 уникальных сочетаний, что подтверждает наши расчёты.

Вычислительная сложность

Вычислительная сложность $O(min⁡(k,n−k))$, т.к. для оптимизации вычисления выбирается минимальное из $k$ или $n−k$, что снижает вычислительную сложность.

Пространственная сложность

Пространственная сложность $O(1)$: Память фиксированная, так как вычисления и хранимые промежуточные значения не увеличиваются с ростом $n$.

---

Применение

Сочетания без повторений имеют широкий спектр применений в различных областях:

1. Математика: Используются для решения комбинаторных задач и формулирования математических теорем.

2. Информатика: Применяются в алгоритмах и структурах данных для обработки комбинаторных данных, например, в задачах перебора вариантов.

3. Статистика: Применяются для анализа данных и расчета вероятностей.

---

Готовые функции в Python

В Python, библиотека itertools предоставляет функцию combinations(iterable, r), которая генерирует все уникальные сочетания длины r из итерируемого объекта iterable. Эта функция удобна для работы с сочетаниями без повторений и включена в стандартную библиотеку Python.

---

Готовые функции в C++

В C++, библиотека <algorithm> предоставляет функцию next_combination(), которая может быть использована для генерации сочетаний без повторений. Однако, эта функция не включена в стандартную библиотеку C++ и требует дополнительного кода для реализации.

---

Псевдокод

Функция Вычислить_Сочетания_Без_Повторений(n, k):
    результат <- 0

    Если n >= k то:
        результат <- Вычислить_Факториал(n) / (Вычислить_Факториал(k) * Вычислить_Факториал(n - k))

    Вернуть результат

Функция Вычислить_Факториал(x):
    результат <- 1

    Для каждого i от 1 до x:
        результат <- результат * i

    Вернуть результат

---

Реализация на Python

Аннотация:
combinations_without_repetition - функция для вычисления количества сочетаний без повторений
n - общее количество элементов
k - размер сочетания
result - результат вычисления количества сочетаний без повторений, вычисляется с помощью формулы

def combinations_without_repetition(n, k):
    if k > n or k < 0:
        return 0

    if k > n - k:
        k = n - k

    result = 1

    for i in range(1, k + 1):
        result *= n - i + 1
        result //= i

    return result

---

Олимпиадная реализация на С++

Аннотация:
n - общее количество элементов
k - размер сочетания
res - результат вычисления количества сочетаний без повторений
num - факториал числа n
denom - произведение факториалов чисел

#include <iostream>
using namespace std; 

long long comb_without_rep(int n, int k) {
    long long res = 1;
    if (n >= k) {
        long long num = 1;
        long long denom = 1;
        for (int i = 1; i <= n; i++) {
            num *= i;
        }
        for (int i = 1; i <= k; i++) {
            denom *= i;
        }
        for (int i = 1; i <= (n - k); i++) {
            denom *= i;
        }
        res = num / denom;
    }
    return res;
}

---

Продуктовая реализация на С++

Аннотация:
factorial - функция для вычисления факториала числа x
x - число, факториал которого нужно вычислить
result - результат вычисления факториала
combinations_without_repetition - функция для вычисления сочетаний без повторений
n - общее количество элементов
k - размер сочетания
result - результат вычисления количества сочетаний без повторений

#include <iostream>
using namespace std; 

long long factorial(int x) {
    long long result = 1;
    for (int i = 1; i <= x; i++) {
        result *= i;
    }
    return result;
}

long long combinations_without_repetition(int n, int k) {
    long long result = 0;
    if (n >= k) {
        result = factorial(n) / (factorial(k) * factorial(n - k));
    }
    return result;
}