Clasa a XI-a · Metoda backtrackingRead in English

Generarea combinărilor în C++

În engleză: Generating combinations

O(n)C++1760 de linii1 exemplu

Ideea

Afișează toate submulțimile cu k elemente ale mulțimii {1, ..., n} (combinări de n luate câte k). Ca să nu obținem aceeași submulțime de mai multe ori, elementele se generează în ordine strict crescătoare: pe poziția poz încercăm doar valori mai mari decât x[poz - 1] și cel mult n - (k - poz), ca să mai rămână loc pentru elementele următoare. Numărul lor este C(n, k) = n! / (k! · (n - k)!).

Descrierea în engleză

Prints all k-element subsets of the set {1, ..., n} (combinations of n taken k at a time). To avoid getting the same subset several times, the elements are generated in strictly increasing order: at position poz we try only values greater than x[poz - 1] and at most n - (k - poz), so there is still room for the next elements. Their number is C(n, k) = n! / (k! · (n - k)!).

Complexitate
O(C(n, k) · k) timp, O(k) memorie
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

4 2

Ieșire așteptată

1 2
1 3
1 4
2 3
2 4
3 4

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

combinari.cpp
/*
 * Titlu: Generarea combinărilor
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează toate submulțimile cu k elemente ale mulțimii {1, ..., n}
 *            (combinări de n luate câte k). Ca să nu obținem aceeași submulțime de mai
 *            multe ori, elementele se generează în ordine strict crescătoare: pe poziția
 *            poz încercăm doar valori mai mari decât x[poz - 1] și cel mult n - (k - poz),
 *            ca să mai rămână loc pentru elementele următoare. Numărul lor este
 *            C(n, k) = n! / (k! · (n - k)!).
 * Complexitate: O(C(n, k) · k) timp, O(k) memorie
 *
 * Exemplu
 * Intrare: 4 2
 * Ieșire:
 * 1 2
 * 1 3
 * 1 4
 * 2 3
 * 2 4
 * 3 4
 */
#include <iostream>
using namespace std;

int n, k, x[20];

void afiseaza()
{
    for (int i = 1; i <= k; i++)
    {
        cout << x[i] << ' ';
    }
    cout << '\n';
}

void back(int poz)
{
    // x[0] = 0, deci pe prima poziție pornim de la 1
    for (int v = x[poz - 1] + 1; v <= n - (k - poz); v++)
    {
        x[poz] = v;
        if (poz == k)
        {
            afiseaza();
        }
        else
        {
            back(poz + 1);
        }
    }
}

int main()
{
    cin >> n >> k;
    back(1);
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.