Comment générer toutes les K-combinaisons à partir de N éléments en C ?

Génération combinatoire : construire des combinaisons en C

Les combinaisons sont des ensembles d'éléments qui manquent d'ordre, et dans cet article, nous nous concentrons sur la génération de tous k combinaisons possibles à partir d'un ensemble de n éléments.

Algorithme

Le code C fourni utilise un algorithme simple :

1. Représentation binaire : Chaque combinaison peut être représenté comme une chaîne binaire, où un bit défini indique la présence du correspondant élément.
2. Initialisation du masque de bits : Créez une chaîne binaire avec k 1 en tête et N-k 0 à la fin.
3. Permutation : Parcourez toutes les permutations possibles de cette chaîne binaire en utilisant la STL prev_permutation fonction.
4. Sortie : Pour chaque permutation, imprimer les indices des éléments correspondant aux bits définis.

Code Implémentation

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

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

Analyse

Cet algorithme profite de l'un- correspondance à un entre les chaînes binaires et les combinaisons. En permutant la représentation binaire, il génère efficacement toutes les combinaisons de masques de bits possibles et donc toutes les combinaisons possibles des éléments.

La complexité de cet algorithme est O(C(n, k)), où C(n, k ) est le nombre de combinaisons de n éléments pris k à la fois.

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!