Комбинаторные алгоритмыCombinatorial Algorithms

Перестановка (permutation) множества из n элементов — это способ упорядочить все n элементов; их ровно n! (n факториал). Сочетание (combination) — это выбор k элементов из n без учёта порядка; их C(n,k) = n!/(k!(n−k)!). Разбиение (partition) числа n — представление n суммой положительных целых чисел, где порядок слагаемых не важен (например, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1). Все три задачи объединяет одно: количество вариантов растёт настолько быстро (факториально или экспоненциально), что для n больше ~15-20 полный перебор физически невозможен — поэтому первый вопрос всегда "а точно ли нужен полный перебор, или подойдёт ДП (2.4.2) / жадный алгоритм (2.4.3)".A permutation of an n-element set is a way to order all n elements; there are exactly n! (n factorial) of them. A combination is a choice of k elements out of n with order ignored; there are C(n,k) = n!/(k!(n−k)!) of them. A partition of a number n is a way to write n as a sum of positive integers where the order of terms doesn't matter (e.g. 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1). All three share one trait: the count of variants grows so fast (factorially or exponentially) that for n above roughly 15-20, brute-force enumeration is physically impossible — so the first question is always "does this actually need full enumeration, or would DP (2.4.2) / a greedy algorithm (2.4.3) do?"

Самый распространённый в C++ способ — std::next_permutation, который переводит перестановку в следующую по лексикографическому порядку (как в словаре: сравниваются последовательности поэлементно). Алгоритм устроен так: найти самый правый индекс i, где a[i] < a[i+1] (это "точка разворота" — если такой нет, текущая перестановка последняя); найти самый правый индекс j > i, где a[j] > a[i]; поменять местами a[i] и a[j]; развернуть суффикс после i (он был убывающим, разворот делает его возрастающим — минимально возможным продолжением).The most common approach in C++ is std::next_permutation, which advances a permutation to the next one in lexicographic order (as in a dictionary: sequences compared element by element). The algorithm works as follows: find the rightmost index i where a[i] < a[i+1] (the "pivot" — if none exists, the current permutation is the last one); find the rightmost index j > i where a[j] > a[i]; swap a[i] and a[j]; reverse the suffix after i (it was decreasing, reversing makes it increasing — the smallest possible continuation).

std::vector<int> a = {1, 2, 3};
do {
    // обработать текущую перестановку a// process the current permutation a
} while (std::next_permutation(a.begin(), a.end())); // O(n) на шаг, O(n!) итераций// O(n) per step, O(n!) iterations

Альтернатива — алгоритм Хипа (Heap's algorithm), генерирующий все перестановки рекурсивно за одну транспозицию на шаг (амортизированно O(1) на перестановку, а не O(n) как у next_permutation), но без лексикографического порядка — если порядок не важен, а важна только скорость генерации, алгоритм Хипа предпочтительнее.An alternative is Heap's algorithm, generating all permutations recursively via one transposition per step (amortized O(1) per permutation rather than next_permutation's O(n)), but without lexicographic order — when the order doesn't matter and only generation speed does, Heap's algorithm is preferable.

Сочетания часто генерируют через битовые маски: подмножество из n элементов кодируется числом от 0 до 2ⁿ−1, где бит i означает "элемент i включён". Перебор всех 2ⁿ подмножеств — это перебор всех чисел от 0 до 2ⁿ−1; чтобы отобрать только сочетания ровно из k элементов, достаточно проверить popcount (число установленных битов) каждой маски.Combinations are often generated via bitmasks: a subset of n elements is encoded as a number from 0 to 2ⁿ−1, where bit i means "element i is included." Enumerating all 2ⁿ subsets is enumerating all numbers from 0 to 2ⁿ−1; to filter down to combinations of exactly k elements, it's enough to check the popcount (number of set bits) of each mask.

for (int mask = 0; mask < (1 << n); ++mask) {
    if (__builtin_popcount(mask) != k) continue; // нужны только сочетания из k элементов// keep only k-element combinations
    for (int i = 0; i < n; ++i)
        if (mask & (1 << i)) /* элемент i выбран *//* element i is chosen */;
}

Более эффективный способ перебрать только маски с ровно k битами (не тратя время на остальные 2ⁿ − C(n,k) масок) — трюк Гослинга: next = mask + (mask & -mask), затем поправка младших битов — даёт следующую по величине маску с тем же числом установленных битов, минуя лишние.A more efficient way to enumerate only the masks with exactly k bits (without wasting time on the remaining 2ⁿ − C(n,k) masks) is Gosper's hack: next = mask + (mask & -mask), followed by a low-bit fixup — it produces the next-largest mask with the same number of set bits, skipping the rest.

Разбиения числа генерируются рекурсивно: разбиение n на слагаемые не больше max — либо взять слагаемое = max и рекурсивно разбить n−max на слагаемые не больше max, либо уменьшить max на 1 и разбить n на слагаемые не больше max−1. Условие "слагаемые не больше max" и есть механизм, который гарантирует отсутствие повторов вида 3+1 и 1+3 — раз порядок не важен, достаточно всегда идти по невозрастанию.Number partitions are generated recursively: partitioning n into parts no larger than max — either take a part equal to max and recursively partition n−max into parts no larger than max, or decrease max by 1 and partition n into parts no larger than max−1. The "parts no larger than max" condition is exactly the mechanism that prevents duplicates like 3+1 and 1+3 — since order doesn't matter, it's enough to always proceed in non-increasing order.

Формулы выше проще проверить на конкретных цифрах, чем удерживать в общем виде — вот та же арифметика на n, которые можно пересчитать в уме.The formulas above are easier to check on concrete numbers than to hold in general form — here's the same arithmetic on n's small enough to redo by hand.

Перестановки: n = 4Permutations: n = 4

Множество {A, B, C, D} имеет 4! = 4·3·2·1 = 24 перестановки. Первые пять в лексикографическом порядке (как их выдаёт std::next_permutation, начиная с отсортированного ABCD): ABCD, ABDC, ACBD, ACDB, ADBC. Переход от ABCD к ABDC — это ровно шаг алгоритма из раздела выше: точка разворота i — это C (последняя позиция, где A[i]<A[i+1], то есть C<D), j — это D (последний элемент правее i, больший C), меняем местами → ABDC, суффикс после i пуст, разворачивать нечего.The set {A, B, C, D} has 4! = 4·3·2·1 = 24 permutations. The first five in lexicographic order (as std::next_permutation produces them, starting from sorted ABCD): ABCD, ABDC, ACBD, ACDB, ADBC. The step from ABCD to ABDC is exactly the algorithm from above: the pivot i is C (the last position where A[i]<A[i+1], i.e. C<D), j is D (the last element right of i that's greater than C), swap them → ABDC, the suffix after i is empty, nothing to reverse.

Сочетания: C(5,2)Combinations: C(5,2)

Сколько способов выбрать 2 элемента из {1,2,3,4,5}, если порядок не важен? C(5,2) = 5!/(2!·3!) = 120/(2·6) = 10. Через последовательное умножение/деление (безопаснее по переполнению, см. "грабли" ниже): C(5,2) = C(5,1)·(5−2+1)/2 = 5·4/2 = 10. Все 10 пар: {1,2} {1,3} {1,4} {1,5} {2,3} {2,4} {2,5} {3,4} {3,5} {4,5} — ровно те маски с popcount=2 из перебора 2⁵=32 подмножеств, о котором говорилось выше.How many ways to choose 2 elements out of {1,2,3,4,5}, order ignored? C(5,2) = 5!/(2!·3!) = 120/(2·6) = 10. Via successive multiply/divide (safer against overflow, see "gotchas" below): C(5,2) = C(5,1)·(5−2+1)/2 = 5·4/2 = 10. All 10 pairs: {1,2} {1,3} {1,4} {1,5} {2,3} {2,4} {2,5} {3,4} {3,5} {4,5} — exactly the popcount=2 masks out of the 2⁵=32 subsets mentioned above.

Сочетания против размещений: n=4, k=2Combinations vs. arrangements: n=4, k=2

Из {1,2,3,4} выбрать 2 элемента без учёта порядка — C(4,2) = 4!/(2!·2!) = 24/4 = 6 вариантов: {1,2} {1,3} {1,4} {2,3} {2,4} {3,4}. Выбрать те же 2 элемента с учётом порядка (размещение) — 4!/(2)! = 24/2 = 12 вариантов: к каждой из 6 пар добавляется второй порядок (например, {1,2} даёт и (1,2), и (2,1)). Ровно тот случай из "граблей" ниже: спутать эти два числа — значит ошибиться ровно в k!=2 раза.Choosing 2 elements from {1,2,3,4} ignoring order — C(4,2) = 4!/(2!·2!) = 24/4 = 6 options: {1,2} {1,3} {1,4} {2,3} {2,4} {3,4}. Choosing the same 2 elements with order (an arrangement) — 4!/(2)! = 24/2 = 12 options: each of the 6 pairs gains a second ordering (e.g. {1,2} yields both (1,2) and (2,1)). Exactly the gotcha below: confusing the two numbers is off by a factor of k!=2.

Разбиения: n = 5Partitions: n = 5

Число 5 раскладывается суммой положительных целых семью способами (порядок слагаемых не важен, поэтому каждое разбиение идёт по невозрастанию): 5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1; 1+1+1+1+1. По рекурсии из раздела выше: разбить(5, max=5) сначала пробует слагаемое 5 → разбить(0, max=5) = пустое разбиение, даёт "5"; затем уменьшает max до 4 и разбивает 5 на слагаемые ≤4 — это в точности разбиения "4+1", "3+2" и так далее, не включающие 5 как слагаемое.The number 5 decomposes into a sum of positive integers seven ways (order doesn't matter, so each partition is listed non-increasing): 5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1; 1+1+1+1+1. Following the recursion above: partition(5, max=5) first tries the part 5 → partition(0, max=5) is the empty partition, giving "5"; then it lowers max to 4 and partitions 5 into parts ≤4 — exactly the partitions "4+1", "3+2", and so on, that don't include 5 as a part.

Комбинаторика быстро упирается в числа, не помещающиеся в 64 бита (20! уже не помещается в int64 при чуть более крупных вариациях), а криптография (RSA, эллиптические кривые) работает с числами в сотни и тысячи бит по построению. Big integer хранится как массив "цифр" в некоторой базе (обычно 2³² или 2⁶⁴ — максимум, что помещается в машинное слово), и базовые операции — это школьная арифметика в столбик, применённая к массиву вместо десятичных цифр.Combinatorics quickly runs into numbers that don't fit in 64 bits (20! already overflows int64 for slightly larger variations), and cryptography (RSA, elliptic curves) works with numbers hundreds or thousands of bits long by design. A big integer is stored as an array of "digits" in some base (usually 2³² or 2⁶⁴ — the largest that fits a machine word), and the basic operations are schoolbook long arithmetic applied to that array instead of decimal digits.

Сложение и вычитание — O(n) по числу limb'ов, с распространением переноса. Умножение школьным способом — O(n²) (каждый limb множится на каждый), поэтому для действительно больших чисел применяют Karatsuba (2.1.2, T(n)=3T(n/2)+O(n) → Θ(n^1.585)) или, для чисел в тысячи бит, умножение через быстрое преобразование Фурье (FFT) за O(n log n). GMP (GNU Multiple Precision) — стандартная библиотека, реализующая именно эту иерархию: школьный метод для маленьких чисел, Karatsuba для средних, FFT-based Toom-Cook/Schönhage-Strassen для по-настоящему больших.Addition and subtraction are O(n) in the number of limbs, with carry propagation. Schoolbook multiplication is O(n²) (every limb multiplied by every other), so for truly large numbers, Karatsuba (2.1.2, T(n)=3T(n/2)+O(n) → Θ(n^1.585)) is used, or, for numbers thousands of bits long, FFT-based multiplication at O(n log n). GMP (GNU Multiple Precision) is the standard library implementing exactly this hierarchy: schoolbook for small numbers, Karatsuba for medium ones, FFT-based Toom-Cook/Schönhage-Strassen for truly large ones.

// сложение двух big integer, представленных как vector<uint32_t> (limb'ы)// adding two big integers represented as vector<uint32_t> (limbs)
std::vector<uint32_t> add(const std::vector<uint32_t>& a, const std::vector<uint32_t>& b) {
    std::vector<uint32_t> result;
    uint64_t carry = 0;
    for (size_t i = 0; i < std::max(a.size(), b.size()) || carry; ++i) {
        uint64_t sum = carry;
        if (i < a.size()) sum += a[i];
        if (i < b.size()) sum += b[i];
        result.push_back(uint32_t(sum));       // младшие 32 бита// low 32 bits
        carry = sum >> 32;                    // перенос в следующий limb// carry into the next limb
    }
    return result;
}