Wie generiert man alle möglichen k Kombinationen von n Elementen in C?

Erstellen aller möglichen k Kombinationen von n Elementen in C

Gegeben eine Menge von ganzen Zahlen von 1 bis n, besteht die Aufgabe darin, und zu generieren Gibt alle möglichen Kombinationen von k unterschiedlich aus Elemente.

Algorithmus:

Dieses Problem kann mit einem bitmaskenbasierten Ansatz gelöst werden. Eine Bitmaske ist eine Darstellung einer Zahl, bei der jedes Bit das Vorhandensein oder Fehlen eines Elements in der Menge anzeigt.

Der Algorithmus funktioniert wie folgt:

1. Generieren Sie eine Bitmaske mit k am Anfang 1s, die die ersten k Elemente in der Kombination darstellen.
2. Ändern Sie die Größe der Bitmaske auf n Bits, wobei die verbleibenden N-K Bits auf gesetzt werden 0.
3. Durchlaufen Sie Bitmasken der Länge n und prüfen Sie jedes Bit.
4. Für jedes auf 1 gesetzte Bit wird das entsprechende ausgegeben Artikel.

Code:

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

void comb(int N, int K)
{
    std::string bitmask(K, 1);
    bitmask.resize(N, 0);

    do {
        for (int i = 0; i < N; ++i) {
            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 generiert Kombinationen durch die Manipulation von Bitmasken, was effizient ist Möglichkeit, Mengen von Elementen darzustellen. Die Zeitkomplexität beträgt O(n^k) für die Generierung aller möglichen Kombinationen.

Das obige ist der detaillierte Inhalt vonWie generiert man alle möglichen k Kombinationen von n Elementen in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!