Comment puis-je générer des combinaisons en C à l'aide de permutations ?

Générer des combinaisons en C à l'aide de permutations simples

En C, vous pouvez générer des combinaisons en utilisant une approche simple impliquant des permutations. Cette méthode nécessite une compréhension du concept de génération de permutation, où l'ordre des éléments compte.

Aperçu de l'algorithme :

1. Créer un vecteur booléen v de taille n, où n est le nombre total d'éléments dans l'ensemble.
2. Pour les r premiers éléments de v, définissez-les sur true. Cette étape sélectionne les r premiers éléments de l'ensemble.
3. Utilisez la fonction next_permutation ou prev_permutation pour générer toutes les permutations du vecteur booléen.
4. Pour chaque permutation, imprimez les indices des éléments correspondant à les vraies valeurs dans v.

Implémentation :

Voici une implémentation de cet algorithme utilisant next_permutation :

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

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> 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;
}

Explication :

La fonction next_permutation génère la prochaine permutation lexicographique du vecteur booléen. En itérant sur le vecteur et en imprimant les indices des vraies valeurs, nous obtenons des combinaisons des r premiers éléments de l'ensemble.

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!