Comment puis-je générer efficacement des combinaisons en C à l'aide de « std :: next_permutation » et « std :: prev_permutation » ?

Génération de combinaisons en C

Introduction au problème

La génération de combinaisons est une opération courante dans divers scénarios de programmation. Elle consiste à créer des ensembles contenant un nombre spécifié d’éléments issus d’une collection plus vaste. Cet article explore comment relever le défi de la génération de combinaisons en C.

Solution avec std::next_permutation

Une approche efficace consiste à exploiter la fonction std::next_permutation de la bibliothèque standard C. Voici une implémentation :

#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;
}

Cette solution commence par créer un tableau de sélection (v) et placer r sélecteurs dans les r dernières positions. La fonction std::next_permutation génère toutes les permutations de ces sélecteurs. Pour chaque permutation, il imprime les membres de l'ensemble correspondant aux positions sélectionnées.

Alternative avec std::prev_permutation

Pour les situations où les combinaisons doivent être sorties dans un format différent ordre, pensez à utiliser std::prev_permutation à la place :

#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;
}

Cette variante alterne l'ordre des combinaisons, rendant le résultat plus facile à interpréter.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!