Wie erzeuge ich alle K-Kombinationen aus N Elementen in C?

Kombinatorische Generierung: Konstruieren von Kombinationen in C

Kombinationen sind Mengen von Elementen, denen es an Ordnung mangelt, und in diesem Artikel konzentrieren wir uns auf die Generierung aller Elemente mögliche k Kombinationen aus einer Menge von n Elemente.

Algorithmus

Der bereitgestellte C-Code verwendet einen einfachen Algorithmus:

1. Binäre Darstellung: Jede Kombination kann als Binärzeichenfolge dargestellt werden, wobei ein gesetztes Bit das Vorhandensein des entsprechenden Bits anzeigt Element.
2. Bitmasken-Initialisierung: Erstellen Sie eine Binärzeichenfolge mit k führenden Einsen und N-k nachgestellten Nullen.
3. Permutation: Durchlaufen Sie alle möglichen Permutationen von Diese Binärzeichenfolge mithilfe der STL prev_permutation Funktion.
4. Ausgabe:Drucken Sie für jede Permutation die Indizes der Elemente aus, die den gesetzten Bits entsprechen.

Code Implementierung

#include <algorithm>
#include <iostream>
#include <string>

void comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's

    // print integers and permute bitmask
    do {
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]) std::cout << " " << i;
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}

int main()
{
    comb(5, 3);
}

Ausgabe

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

Analyse

Dieser Algorithmus nutzt die eine- Eins-zu-eins-Korrespondenz zwischen binären Zeichenfolgen und Kombinationen. Durch Permutation der binären Darstellung werden effektiv alle möglichen Bitmaskenkombinationen und damit alle möglichen Kombinationen der Elemente generiert.

Die Komplexität dieses Algorithmus ist O(C(n, k)), wobei C(n, k ) ist die Anzahl der Kombinationen von n Elementen, die k gleichzeitig genommen werden.

Das obige ist der detaillierte Inhalt vonWie erzeuge ich alle K-Kombinationen aus N Elementen in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!