Основные элементы комбинаторики Комбинаторика

bool next_permutation(iterator begin, iterator end);

//Преобразует перестановку в предыдущую лексикографически
//Если перестановка уже является минимальной, возвращает false
bool prev_permutation(iterator begin, iterator end);
Сочетания
Сочетанием из nn по kk называется любой набор из nn элементов, выбранных из данных kk элементов. Например, рассмотрим множество 1,2,3,41,2,3,4. Существует 6 сочетаний по 2 из этого множества:

• 
  1,21,2.
  
• 
  1,31,3.
  
• 
  1,41,4.
  
• 
  2,32,3.
  
• 
  2,42,4.
  
• 
  3,43,4.
  

Число возможных сочетаний из nn по kk обозначается CknCnk и вычисляется по формуле
Ckn=n!k!∗(n−k)!Cnk=n!k!∗(n−k)!
Число сочетаний очень часто встречается в задачах по программированию. Существуют два способа его вычисления:
Наивный
Используется в случаях, когда нужно посчитать небольшое количество CknCnk за O(N)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.
ДП
Выразим CknCnk рекурсивно. Рассмотрим последний (nn-ый) элемент: все сочетания можно разделить на две группы: те которые включают его, и те которые не включают. Заметим, что все сочетания первой группы содержат k−1k−1 элементов из первых n−1n−1, а все сочетания второй группы: kk из первых n−1n−1. Значит,
Ckn=Ckn−1+Ck−1n−1Cnk=Cn−1k+Cn−1k−1
Таким образом мы можем рассчитать значения CknCnk для всех n≤Nn≤N и k≤Kk≤K за O(NK)O(NK).
Реализация на С++ (значения в поле по модулю 109+7109+7):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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