Бүх $K$-комбинацыг үүсгэх¶

Энэ өгүүлэлд бид бүх $K$-комбинацыг үүсгэх бодлогыг авч үзнэ. $N$ ба $K$ натурал тоо өгөгдсөн, $1$-ээс $N$ хүртэлх тоонуудын олонлогийг авч үзье. Даалгавар нь бүх $K$ хэмжээтэй дэд олонлог-ийг гаргах явдал юм.

Дараагийн лексикографын $K$-комбинацыг үүсгэх¶

Эхлээд бид тэдгээрийг лексикографын дарааллаар үүсгэнэ. Үүний алгоритм энгийн. Эхний комбинац нь ${1, 2, ..., K}$ байна. Одоо үүний дараа лексикографын дарааллаар шууд орох комбинацыг хэрхэн олохыг харцгаая. Үүний тулд бид одоогийн комбинацаа авч үзэж, боломжит хамгийн их утгадаа хараахан хүрээгүй хамгийн баруун талын элементийг олно. Энэ элементийг олмогц бид түүнийг $1$-ээр нэмэгдүүлж, дараагийн бүх элементэд хамгийн бага хүчинтэй утгыг ононо.

bool next_combination(vector<int>& a, int n) {
    int k = (int)a.size();
    for (int i = k - 1; i >= 0; i--) {
        if (a[i] < n - k + i + 1) {
            a[i]++;
            for (int j = i + 1; j < k; j++)
                a[j] = a[j - 1] + 1;
            return true;
        }
    }
    return false;
}

Зэргэлдээ комбинацууд нэг элементээр ялгаатай байхаар бүх $K$-комбинацыг үүсгэх¶

Энэ удаад бид зэргэлдээ комбинацууд яг нэг элементээр ялгаатай байх дарааллаар бүх $K$-комбинацыг үүсгэхийг хүсэж байна.

Үүнийг Грэй код ашиглан бодож болно: Хэрэв бид дэд олонлог бүрд битмаск оноовол Грэй кодоор эдгээр битмаскуудыг үүсгэж, тэдгээрээр давтах замаар хариугаа олж болно.

$K$-комбинац үүсгэх даалгаврыг мөн Грэй код ашиглан өөр аргаар бодож болно: $0$-ээс $2^N - 1$ хүртэлх тоонуудын Грэй кодыг үүсгэж, зөвхөн $K$ ширхэг $1$ агуулсан кодуудыг үлдээ. Гайхалтай баримт нь $K$ тавигдсан биттэй гарсан дараалалд дурын хоёр хөрш маск (эхний ба сүүлийн маскийг оруулаад — циклик утгаараа хөрш) яг хоёр битээр ялгаатай байх бөгөөд энэ нь бидний зорилго юм (нэг тоо хасах, нэг тоо нэмэх).

Үүнийг батлая:

Баталгааны хувьд бид $G(N)$ дараалал ($N$-р Грэй кодыг илэрхийлэх)-г дараах байдлаар олж болох баримтыг эргэн санана:

$$G(N) = 0G(N-1) \cup 1G(N-1)^\text{R}$$

Өөрөөр хэлбэл $N-1$-ийн Грэй код дарааллыг авч, гишүүн бүрийн өмнө $0$ угтвар нэм. Мөн $N-1$-ийн урвуу Грэй код дарааллыг авч, маск бүрийн өмнө $1$ угтвар нэмээд, эдгээр хоёр дарааллыг нийлүүл.

Одоо бид баталгаагаа гаргаж болно.

Эхлээд эхний ба сүүлийн маск яг хоёр битээр ялгаатайг батлана. Үүний тулд $G(N)$ дарааллын эхний маск нь $N-K$ ширхэг $0$, дараа нь $K$ ширхэг $1$ хэлбэртэй байхыг тэмдэглэхэд хангалттай. Эхний бит $0$ болж тавигдах ба дараа нь $(N-K-1)$ ширхэг $0$, дараа нь $K$ тавигдсан бит дагах ба сүүлийн маск нь $1$, дараа нь $(N-K)$ ширхэг $0$, дараа нь $K-1$ ширхэг $1$ хэлбэртэй байна. Математик индукцийн зарчмыг хэрэглэж, $G(N)$-ийн томьёог ашиглах нь баталгааг дуусгана.

Одоо бидний даалгавар бол дурын хоёр зэргэлдээ код мөн яг хоёр битээр ялгаатайг харуулах явдал бөгөөд үүнийг Грэй код үүсгэх рекурсив тэгшитгэлээ авч үзэн хийж болно. $G(N-1)$-ээр үүссэн хоёр хагасын агуулга үнэн гэж үзье. Одоо бид залгаа дээр (эдгээр хоёр хагасыг нийлүүлснээр) үүссэн шинэ дараалсан хос мөн хүчинтэй буюу яг хоёр битээр ялгаатайг батлах хэрэгтэй.

Бид эхний хагасын сүүлийн маск ба хоёр дахь хагасын эхний маскийг мэддэг тул үүнийг хийж болно. Эхний хагасын сүүлийн маск нь $1$, дараа нь $(N-K-1)$ ширхэг $0$, дараа нь $K-1$ ширхэг $1$ байна. Хоёр дахь хагасын эхний маск нь $0$, дараа нь $(N-K-2)$ ширхэг $0$ дагах ба дараа нь $K$ ширхэг $1$ байна. Тиймээс хоёр маскийг харьцуулбал бид яг хоёр ялгаатай бит олно.

Дараах нь бүх $2^{n}$ боломжит дэд олонлогийг үүсгэж, $K$ хэмжээтэй дэд олонлогуудыг олж ажилладаг гэнэн хэрэгжүүлэлт юм.

int gray_code (int n) {
    return n ^ (n >> 1);
}

int count_bits (int n) {
    int res = 0;
    for (; n; n >>= 1)
        res += n & 1;
    return res;
}

void all_combinations (int n, int k) {
    for (int i = 0; i < (1 << n); i++) {
        int cur = gray_code (i);
        if (count_bits(cur) == k) {
            for (int j = 0; j < n; j++) {
                if (cur & (1 << j))
                    cout << j + 1;
            }
            cout << "\n";
        }
    }
}

Зөвхөн хүчинтэй комбинацуудыг байгуулахад л хандаж, ингэснээр $O\left(N \cdot \binom{N}{K}\right)$-д ажилладаг илүү үр ашигтай хэрэгжүүлэлт байдгийг дурдах нь зүйтэй, гэвч энэ нь мөн чанараараа рекурсив бөгөөд $N$-ийн бага утгуудын хувьд өмнөх шийдлээс магадгүй том тогтмолтой.

Хэрэгжүүлэлтийг дараах томьёоноос гаргана:

$$G(N, K) = 0G(N-1, K) \cup 1G(N-1, K-1)^\text{R}$$

Энэ томьёог Грэй кодыг тодорхойлох ерөнхий тэгшитгэлийг өөрчилж олох ба тохирох элементүүдээс дэд дарааллыг сонгож ажилладаг.

Түүний хэрэгжүүлэлт дараах байдалтай:

vector<int> ans;

void gen(int n, int k, int idx, bool rev) {
    if (k > n || k < 0)
        return;

    if (!n) {
        for (int i = 0; i < idx; ++i) {
            if (ans[i])
                cout << i + 1;
        }
        cout << "\n";
        return;
    }

    ans[idx] = rev;
    gen(n - 1, k - rev, idx + 1, false);
    ans[idx] = !rev;
    gen(n - 1, k - !rev, idx + 1, true);
}

void all_combinations(int n, int k) {
    ans.resize(n);
    gen(n, k, 0, false);
}