Comment générer toutes les k combinaisons de n éléments en C ?

Algorithme pour générer toutes les k combinaisons de n éléments en C

La tâche à accomplir est de créer un programme qui génère et affiche tous les combinaisons de k personnes distinctes à partir d’un ensemble de n individus. Ceci peut être réalisé à l'aide d'un algorithme de génération de combinaison, qui fonctionne comme suit :

Algorithme :

1. Initialiser un masque de bits avec une séquence de K 1 en tête : Ce masque de bits signifie que les K premières personnes de l'ensemble sont initialement affectées au combinaison.
2. Redimensionnez le masque de bits à N bits, en ajoutant N-K 0 à droite : Cette étape étend le masque de bits pour couvrir toutes les n personnes de l'ensemble.
3. Itérer à travers toutes les permutations possibles du masque de bits : Chaque permutation représente une combinaison différente de K personnes.

4. Pour chaque permutation :

   • Extraire les indices des bits définis dans le masque de bits. Ces indices représentent les membres de la combinaison actuelle.
   • Imprimez la combinaison.
5. Répétez l'étape 3 jusqu'à ce que toutes les permutations soient épuisées : Ceci aura généré toutes les combinaisons possibles de K personnes à partir de l'ensemble des n.

Mise en œuvre dans C :

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

Exemple de sortie :

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

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!