kz-maxx

RU KZ
← Басты бет

Сочетания

n элементтен k элемент таңдау, C(n,k) формуласы, генерация және санау

Сочетание деген не?

Сочетание — n элементтің ішінен k элемент таңдау. Мұнда порядок маңызды емес.

n элементтен k элемент таңдаймыз
порядок есептелмейді

Мысалы, сандар бар: 

1 2 3

2 элементтен тұратын сочетания: 

1 2
1 3
2 3

Мұнда 1 2 және 2 1 — бірдей сочетание.

Белгіленуі

Сочетания саны былай белгіленеді: 

C(n, k)

Немесе: 

n choose k

Мағынасы:

n элементтен k элементті неше түрлі таңдауға болады

Сочетания формуласы

Формула: 

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

Неге порядок маңызды емес?

3 адамның ішінен 2 адам таңдайық: 

A B C

Сочетания: 

A B
A C
B C

A B және B A бірдей деп саналады.

Егер порядок маңызды болса, онда бұл сочетания емес, размещения немесе перестановки болады.

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

Тип Мағынасы Порядок маңызды ма?
Сочетания n ішінен k таңдау Жоқ
Размещения n ішінен k таңдап, орналастыру Иә
Перестановки барлық 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) мәндері өте тез үлкен болып кетеді.

Mod бойынша санау

Задачаларда көбіне керек: 

C(n, k) mod MOD

Онда DP ішінде қосқаннан кейін mod аламыз. 

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

Код: C(n,k) DP mod арқылы

#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) factorial арқылы

Егер n үлкен және query көп болса, факториалдарды алдын ала санау ыңғайлы: 

fact[i] = i!

Сонда: 

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

Mod бойынша бөлу inverse арқылы жасалады.

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

Простое MOD бойынша inverse үшін қолданамыз: 

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

Генерация идеясы

Answer-ды рекурсивно құрамыз. Әр қадамда келесі санды таңдаймыз.

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

Bitmask арқылы генерация

Егер n кішкентай болса, барлық mask-тарды 0-ден 2^n - 1-ге дейін қарауға болады.

Mask ішінде bit 1 болса, элемент таңдалған деген сөз.

mask = 10110
1 тұрған позициялар таңдалған

k өлшемді сочетание үшін bit саны k-ға тең болуы керек.

Код: bitmask арқылы сочетания

#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 үшін жарайды. Себебі барлық mask саны 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 үлкен Factorial + inverse
Барлық сочетания шығару керек Рекурсия / backtracking
n кішкентай және subset-пен жұмыс ыңғайлы Bitmask
STL арқылы оңай әдіс керек next_permutation

Асимптотика

Метод Уақыт Память
Паскаль DP O(n²) O(n²)
Factorial build O(n log MOD) O(n)
build кейін бір C(n,k) query O(1) O(n)
Барлық сочетания генерациясы O(C(n,k) * k) O(k)
Bitmask O(2^n * n) O(1)

Типтік қателер

  • Сочетания мен перестановки шатастыру
  • 1 2 және 2 1 екі түрлі сочетание деп ойлау
  • C(n,0)=1 және C(n,n)=1 базаларын ұмыту
  • C(n,k)-ны обычный түрде санап overflow алу
  • Үлкен n үшін factorial-ды mod-сыз қолдану
  • Mod бойынша обычный бөлу жасау
  • Генерацияда 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;
}

Ең бастысы

сочетание = n ішінен k таңдау
порядок маңызды емес
C(n,k) = n! / (k! * (n-k)!)
C(n,k) = C(n-1,k-1) + C(n-1,k)
барлық сочетания-ны рекурсиямен генерация жасау ыңғайлы