Wie kann ich mit „std::next_permutation' und „std::prev_permutation' effizient Kombinationen in C generieren?

Erzeugen von Kombinationen in C

Problemeinführung

Das Erzeugen von Kombinationen ist eine häufige Operation in verschiedenen Programmierszenarien. Dabei werden Sätze erstellt, die eine bestimmte Anzahl von Elementen aus einer größeren Sammlung enthalten. In diesem Artikel wird untersucht, wie Sie die Herausforderung der Generierung von Kombinationen in C bewältigen können.

Lösung mit std::next_permutation

Ein effektiver Ansatz besteht darin, die Funktion std::next_permutation zu nutzen aus der C-Standardbibliothek. Hier ist eine Implementierung:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

Diese Lösung beginnt mit der Erstellung eines Auswahlarrays (v) und der Platzierung von r Selektoren an den letzten r Positionen. Die Funktion std::next_permutation generiert alle Permutationen dieser Selektoren. Für jede Permutation werden die Satzmitglieder gedruckt, die den ausgewählten Positionen entsprechen.

Alternative mit std::prev_permutation

Für Situationen, in denen die Kombinationen anders ausgegeben werden sollen Reihenfolge, ziehen Sie stattdessen die Verwendung von std::prev_permutation in Betracht:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

Diese Variante ändert die Reihenfolge der Kombinationen, wodurch Die Ausgabe ist leichter zu interpretieren.

Das obige ist der detaillierte Inhalt vonWie kann ich mit „std::next_permutation' und „std::prev_permutation' effizient Kombinationen in C generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!