La création de tous les possibles k combinaisons de n objets en C++

Je suppose que vous vous posez à propos des combinaisons en combinatoire sens (c'est l'ordre des éléments n'a pas d'importance, de sorte [1 2 3] est le même que [2 1 3]). L'idée est assez simple, si vous comprenez induction /récursivité: pour obtenir tous les K-élément de combinaisons, vous choisissez d'abord premier élément d'une combinaison de l'ensemble existant de gens, et ensuite vous "concaténer" cet élément de départ, avec toutes les combinaisons possibles de K-1 personnes produite à partir d'éléments que réussir l'élément initial.

Comme un exemple, disons que nous voulons prendre toutes les combinaisons de 3 personnes à partir d'un ensemble de 5 personnes. Ensuite toutes les combinaisons possibles de 3 personnes peut être exprimée en fonction de toutes les combinaisons possibles de 2 personnes:

comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }

Voici le code C++ qui met en œuvre cette idée:

#include <iostream>
#include <vector>

using namespace std;

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v) {
  static int count = 0;
  cout << "combination no " << (++count) << ": [ ";
  for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
  cout << "] " << endl;
}

void go(int offset, int k) {
  if (k == 0) {
    pretty_print(combination);
    return;
  }
  for (int i = offset; i <= people.size() - k; ++i) {
    combination.push_back(people[i]);
    go(i+1, k-1);
    combination.pop_back();
  }
}

int main() {
  int n = 5, k = 3;

  for (int i = 0; i < n; ++i) { people.push_back(i+1); }
  go(0, k);

  return 0;
}

Et voici la sortie pour N = 5, K = 3:

combination no 1:  [ 1 2 3 ] 
combination no 2:  [ 1 2 4 ] 
combination no 3:  [ 1 2 5 ] 
combination no 4:  [ 1 3 4 ] 
combination no 5:  [ 1 3 5 ] 
combination no 6:  [ 1 4 5 ] 
combination no 7:  [ 2 3 4 ] 
combination no 8:  [ 2 3 5 ] 
combination no 9:  [ 2 4 5 ] 
combination no 10: [ 3 4 5 ] 

Si le nombre de jeu serait dans un rayon de 32, 64 ou une machine natif primitif de taille, alors vous pouvez le faire avec une simple manipulation de bits.

template<typename T>
void combo(const T& c, int k)
{
    int n = c.size();
    int combo = (1 << k) - 1;       //k bit sets
    while (combo < 1<<n) {

        pretty_print(c, combo);

        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    }
}

cet exemple appelle pretty_print() de la fonction par l'ordre du dictionnaire.

Par exemple. Vous voulez avoir 6C3 et en supposant que l'actuelle "combo" est 010110.
Évidemment, le prochain combo DOIT être 011001.
011001 est :
010000 | 001000 | 000001

010000 : supprimé en permanence 1s de côté LSB.
001000 : set 1 sur le côté de la permanence 1s de côté LSB.
000001 : déplacé en continu 1s de LSB vers la droite et retirez LSB bit.

int x = combo & -combo;

cette obtient le plus bas 1.

int y = combo + x;

ceci élimine en permanence 1s de LSB côté et de l'ensemble 1 sur le côté de celui-ci (dans le cas ci-dessus, 010000 | 001000)

int z = (combo & ~y)

cela vous donne en permanence à 1s de côté LSB (000110).

combo = z / x;
combo >> =1;

c'est pour "déplacé en continu 1s de LSB vers la droite et retirez LSB peu".

De sorte que le travail final est de OU de y au-dessus.

combo |= y;

Un simple exemple concret :

#include <bits/stdc++.h>

using namespace std;

template<typename T>
void pretty_print(const T& c, int combo)
{
    int n = c.size();
    for (int i = 0; i < n; ++i) {
        if ((combo >> i) & 1)
            cout << c[i] << ' ';
    }
    cout << endl;
}

template<typename T>
void combo(const T& c, int k)
{
    int n = c.size();
    int combo = (1 << k) - 1;       //k bit sets
    while (combo < 1<<n) {

        pretty_print(c, combo);

        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    }
}

int main()
{
    vector<char> c0 = {'1', '2', '3', '4', '5'};
    combo(c0, 3);

    vector<char> c1 = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    combo(c1, 4);
    return 0;
}

résultat :

1 2 3 
1 2 4 
1 3 4 
2 3 4 
1 2 5 
1 3 5 
2 3 5 
1 4 5 
2 4 5 
3 4 5 
a b c d 
a b c e 
a b d e 
a c d e 
b c d e 
a b c f 
a b d f 
a c d f 
b c d f 
a b e f 
a c e f 
b c e f 
a d e f 
b d e f 
c d e f 
a b c g 
a b d g 
a c d g 
b c d g 
a b e g 
a c e g 
b c e g 
a d e g 
b d e g 
c d e g 
a b f g 
a c f g 
b c f g 
a d f g 
b d f g 
c d f g 
a e f g 
b e f g 
c e f g 
d e f g 

J'ai écrit une classe en C# pour gérer des fonctions pour travailler avec le coefficient binomial, qui est le type de problème que votre problème relève de. Il effectue les tâches suivantes:

1. Sorties de tous les K-index dans un beau format pour tout N de choisir K pour un fichier. Le K-index peut être substitué avec plus descriptif, les cordes ou les lettres. Cette méthode permet de résoudre ce type de problème tout à fait banale.

2. Convertit le K-index de l'index approprié d'une entrée dans la triés coefficient binomial table. Cette technique est beaucoup plus rapide que les plus âgés publié des techniques qui s'appuient sur l'itération. Il le fait en utilisant une propriété mathématique inhérente dans le Triangle de Pascal. Mon livre parle de cela. Je crois que je suis le premier à découvrir et publier cette technique.

3. Convertit l'indice triés coefficient binomial tableau correspondant de la K-index. Je crois qu'il est également plus rapide que les autres solutions.

4. Utilise Marque Dominus méthode pour calculer le coefficient binomial, ce qui est beaucoup moins susceptibles de déborder et travaille avec de plus grands nombres.

5. La classe est écrit en .NET C# et fournit un moyen de gérer les objets en rapport avec le problème (le cas échéant) à l'aide d'une liste générique. Le constructeur de cette classe prend une valeur booléenne appelée InitTable que lorsque la volonté réelle de créer une liste générique pour contenir les objets gérés. Si cette valeur est fausse, alors il ne va pas créer la table. La table n'a pas besoin d'être créé afin d'effectuer les 4 méthodes ci-dessus. Méthodes d'accès sont fournis pour accéder à la table.

6. Il est associé à une classe de test qui montre comment utiliser la classe et ses méthodes. Il a été testé avec les 2 cas, et il n'y a pas de bugs connus.

À lire sur cette classe et télécharger le code, voir Tablizing Le Binôme Coeffieicent.

Il devrait être assez simple à port la classe au cours de C++.

La solution à votre problème consiste à générer le K-index pour chaque N choisir K cas. Par exemple:

int NumPeople = 10;
int N = TotalColumns;
//Loop thru all the possible groups of combinations.
for (int K = N - 1; K < N; K++)
{
   //Create the bin coeff object required to get all
   //the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   int[] KIndexes = new int[K];
   BC.OutputKIndexes(FileName, DispChars, "", " ", 60, false);
   //Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      //Get the k-indexes for this combination, which in this case
      //are the indexes to each person in the problem set.
      BC.GetKIndexes(Loop, KIndexes);
      //Do whatever processing that needs to be done with the indicies in KIndexes.
      ...
   }
}

La OutputKIndexes méthode peut également être utilisée à la sortie de la K-index d'un fichier, mais il va utiliser un fichier différent pour chaque N choisir K cas.

Derrière le lien ci-dessous est un générique de C# réponse à ce problème: Comment faire pour formater toutes les combinaisons à partir d'une liste d'objets. Vous pouvez limiter les résultats que pour la longueur de k assez facilement.

https://stackoverflow.com/a/40417765/2613458