Générer combinaisons en c++
J'ai été la recherche d'un code source pour la génération de combinaison à l'aide de c++. J'ai trouvé des codes pour cela, mais ce qui est bon pour seulement certains nombre de données prédéfinis. Quelqu'un peut-il me donner quelques conseils, ou peut-être une idée pour générer de la combinaison. Par exemple, supposons que l'ensemble S = { 1, 2, 3, ...., n} et on choisir r= 2 hors de lui. L'entrée serait n
et r
.Dans ce cas, le programme va générer des tableaux de longueur deux, comme 5 2 sorties, 1 2, 1 3, etc.. j'ai eu de la difficulté dans la construction de l'algorithme. Il m'a fallu un mois de réflexion à ce sujet.
- Je ne comprends pas vraiment ce que vous voulez. Compte tenu de l'ensemble
S
et l'entrée 2, voulez-vous de toutes les combinaisons de 2 et de chaque élément deS
dans un tableau de longueur du tableau 2? - Vous avez besoin d'être plus précis, ce genre de combinaisons que vous souhaitez. Par exemple, avec S = {1, 2} et r=2, voulez-vous {1,2} et {2,1}, ou {1,1} et {2,2}, ou même juste {1,2}?
- Je pense qu'il veut ceci: en.wikipedia.org/wiki/Combination. {1,2} {2,1} sont les mêmes, et {1,1} et {2,2} ne sont pas possibles.
- Pour lisible algorithmes, vous pouvez regarder dans la documentation Python: docs.python.org/library/itertools.html
- Le répondre c'est une recherche google à l'écart
- il y a un élaborer la réponse ici stackoverflow.com/questions/127704/...
- Si je comprends bien, vous êtes à la recherche d'une sorte d'algorithme générique, non? Avec r=2, vous ne disposez que de deux boucles imbriquées, mais avec r=3, vous avez de trois, de sorte que serait grosso modo un algorithme différent, et vous êtes à la recherche d'un algorithme unique qui gère tous les cas, jusqu'à r=count. Droit? Est que votre question?
- Oui, @MrLister. Je suis à la recherche d'un seul algorithme en C++ où la sortie lorsque nous entrons n le nombre d'éléments de l'ensemble et r la longueur du tableau.
- Je ne suis pas préoccupé par la permutation, de toute façon, c'est ce que je voulais savoir: si nous entrons n= 5; c'est 1 ,2, 3 ,4 5. et r = 1, nous avons obtenu la sortie 1,2,3,4,5. mais si r=5, on a 1 2 3 4 5. changer les entrées n= 5 r= 2, nous avons : 1 2 , 1 3, 1 4, 1 5 , 2 3 , etc... où l'on peut vérifier à l'aide de la formule de combinaison..
- Je ne pense pas que l'on a accepté la réponse est un choix.
Vous devez vous connecter pour publier un commentaire.
Une manière simple à l'aide de
std::next_permutation
:ou une légère variation qui affiche les résultats dans un plus facile de suivre l'ordre:
Un peu d'explication:
Il fonctionne en créant un "tableau de sélection" (
v
), où l'on placer
sélecteurs, puis nous créons de toutes les permutations de ces sélecteurs, et d'imprimer l'ensemble correspondant membre si elle est sélectionnée dans le courant de permutation dev
. Espérons que cette aide.std::next_permutation
effectue au plusn/2
swaps. La boucle externe fonctionneCr(n, r)
fois, et nous avons aussi une boucle interne quiO(n)
.k
den
. afin de permutation peut échouer ici, mais si nous devons former des combinaisons à l'aide de tous lesn
personnages , c'est correct .k
den
, et ce programme est exactement ce que fait. Permutation est seulement utilisé pour générer toutes les permutations de la sélection.if(v[i])
vérifier si vous remplissezv
dev.begin()
àv.end()-n+r
au lieu dev.begin()+n-r
àv.end()
.prev_permutation
dans ce cas.prev_permutation
😉 Mettra à jour la réponse, merci.Vous pouvez mettre en œuvre si vous notez que pour chaque niveau r vous sélectionnez un numéro de 1 à n.
En C++, nous avons besoin de 'manuellement' garder à l'état entre les appels qui produit des résultats (une combinaison): alors, nous construisons une classe que sur la construction de l'initialiser l'état, et a un membre qui à chaque appel renvoie la combinaison bien qu'il existe des solutions: par exemple
test de sortie:
for (int j=i+1;j<=5;j++)
ma solution simple et efficace basée sur les algorithmes de la Prof. Nathan Wodarz:
puis la sortie est:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Je vous suggère de trouver comment vous le feriez sur du papier vous-même et en déduire pseudo-code de cette. Après cela, il vous suffit de décider de la façon d'encoder et stocker les données manipulées.
Ex:
Vous pouvez utiliser la récursivité lequel choisir N+1 combinaisons que vous choisissez N combinaisons puis ajouter 1. Le 1 vous ajoutez doit toujours être après la dernière une de vos N, donc si votre N comprend le dernier élément, il n'y a pas de N+1 combinaisons associées.
Peut-être pas la solution la plus efficace, mais il devrait fonctionner.
De Base serait le cas de la cueillette de 0 ou 1. Vous pouvez vous emparer de 0 et un ensemble vide. À partir d'un ensemble vide, vous pouvez supposer que les itérateurs de travail entre les éléments, et pas à eux.
Code est similaire à la génération de chiffres binaires. Gardez une structure de données, un tableau perm[], dont la valeur à l'index, je vais dire si le ième élément du tableau est inclus ou pas. Et aussi garder un nombre variable. Chaque fois que count == longueur de la combinaison, les éléments d'impression basé sur perm[].
c'est une méthode récursive, que vous pouvez utiliser sur n'importe quel type. vous pouvez effectuer une itération sur une instance de Combinaisons de classe (par exemple, ou get() vecteur avec toutes les combinaisons, chaque combinaison est un vecteur d'objets. C'est écrit en C++11.
Fichier de Test:
de sortie est :
0, 1, 2,
0, 1, 3,
0, 1, 4,
0, 1, 5,
0, 2, 3,
0, 2, 4,
0, 2, 5,
0, 3, 4,
0, 3, 5,
0, 4, 5,
1, 2, 3,
1, 2, 4,
1, 2, 5,
1, 3, 4,
1, 3, 5,
1, 4, 5,
2, 3, 4,
2, 3, 5,
2, 4, 5,
3, 4, 5,
(1, 0.4, 5), (2, 0.7, 5),
(1, 0.4, 5), (3, 0.1, 2),
(1, 0.4, 5), (4, 0.66, 99),
(2, 0.7, 5), (3, 0.1, 2),
(2, 0.7, 5), (4, 0.66, 99),
(3, 0.1, 2), (4, 0.66, 99),
Pour le cas particulier de (n choisir r), où r est une constante fixe, on peut écrire r boucles imbriquées pour en arriver à la situation. Parfois, lorsque r n'est pas fixe, on peut avoir un autre cas particulier (n choisir n-r), où r est encore une constante fixe. L'idée est que chaque combinaison est l'inverse de la combinaisons de (n choisir r). Donc on peut de nouveau utiliser r de boucles imbriquées, mais d'inverser la solution:
Vous pouvez simplement utiliser pour les boucles si r est petit, ici, r = 2, donc deux boucles for: