** Mis à jour le 14/09: l'exemple d'implémentation enseigné dans la section commentaire est publié à la fin de cet article (C ++, Python) **
Je voulais faire une combinaison qui permette la duplication en C ++ à laquelle je ne suis pas habitué, j'ai donc beaucoup cherché, mais je ne pouvais pas la trouver facilement. Il existe un «ordre» qui permet les doublons, et une formule qui calcule le nombre total de combinaisons en double ($ \ small_n H_r $ que j'ai appris au collège), mais le code qui peut énumérer les combinaisons en double n'a pas été déplacé.
Quand je l'ai recherché, il semble que ʻitertoolscontienne normalement une fonction appeléecombination_with_replacement ()` en Python, donc ce code (https://docs.python.org/ja/3/library/itertools.html) ), Et l'a réimplémenté en C ++.
Si vous avez des erreurs ou des améliorations, veuillez nous en informer.
Tout d'abord, à titre d'exemple, considérons une énumération de combinaison lors de l'extraction d'éléments $ 2 $ de l'ensemble $ \ left \ {1, 2, 3 \ right \} $, permettant la duplication. Le flux lui-même est simple et ressemble à ceci:
En d'autres termes, en général, si vous souhaitez autoriser la duplication de l'ensemble $ \ Omega $ et extraire des éléments $ n $, vous pouvez dupliquer $ \ Omega $ en $ n $ et extraire une combinaison unique de leur produit cartésien. Ce sera.
Tout d'abord, implémentez-le en générant le produit cartésien. Il semble qu'il y ait aussi une fonction appelée product () de ʻitertools` en Python, mais je n'ai pas pu rattraper la notation d'inclusion de double liste dans le code source, j'ai donc implémenté le produit cartésien dans Golang. J'ai fait référence au code de la personne qui est (https://qiita.com/tesujiro/items/2e41e1159948dc90c3d9). Cette personne écrit généralement le code pour calculer le produit cartésien entre plusieurs ensembles de $ \ Omega_1, \ Omega_2, \ Omega_3, \ ldots $.
Dans mon implémentation cette fois, "Autoriser les doublons de $ \ Omega $ et extraire $ n $ pièces", donc $ \ Omega_1 = \ Omega, \ Omega_2 = \ Omega, \ Omega_3 = en produit cartésien général Équivalent à \ Omega, \ ldots, \ Omega_n = \ Omega $. Au fur et à mesure que la valeur de $ n $ augmente, il devient difficile de dupliquer $ \ Omega $ du nombre de $ n $ et de l'affecter à l'argument, donc $ n $ est compté avec l'argument répéter. Je vais. Tout d'abord, le code est affiché ci-dessous.
python
#include <bits/stdc++.h>
using namespace std;
template<typename T>
vector<vector<T>> productRecurse(vector<T>, int, vector<vector<T>>);
//produit cartésien
template<typename T>
vector<vector<T>> product(vector<T> choices, int repeat) {
vector<vector<T>> emptyResult(1, vector<T>());//Liste vide pour stocker les combinaisons
return productRecurse(choices, repeat, emptyResult);
}
template<typename T>
vector<vector<T>> productRecurse(vector<T> choices, int repeat, vector<vector<T>> result) {
if (repeat == 0) {return result;}//Renvoie la réponse lorsque le produit cartésien est terminé
vector<vector<T>> provisionalResult;//Produit cartésien en cours de création
for (vector<T> re: result) {
for (T c: choices) {
vector<T> temp = re;
temp.push_back(c);
provisionalResult.push_back(temp);
}
}
return productRecurse(choices, repeat - 1, provisionalResult);
}
En expliquant le code ci-dessus, considérons à nouveau comme exemple pour dupliquer l'ensemble $ \ left \ {1, 2, 3 \ right \} $ en $ 2 $ pour créer un produit cartésien. Le flux lors de l'appel de product (choix = {1, 2, 3}, repeat = 2) est le suivant.
product (choix = {1, 2, 3}, repeat = 2).productRecurse (choix = {1, 2, 3}, repeat = 2, result = {{}}) est appelé.provisoireResult = {{1}, {2}, {3}}.productRecurse (choix = {1, 2, 3}, repeat = 1, result = {{1}, {2}, {3}}) est appelé.provisoireResult = {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3 , 2}, {3, 3}} .repeat == 0, l'argument result est le produit cartésien final.En Python, cela signifie que la partie qui peut être incluse dans la liste est répétée de manière récursive. Exécutons-le réellement.
python
int main(){
vector<int> choices = {1, 2, 3};
int repeat = 2;
vector<vector<int>> answer = product(choices, repeat);
for (int i = 0; i < answer.size(); i++) {
cout << answer[i][0] << " " << answer[i][1] << endl;
}
}
Comme calculé manuellement, vous pouvez voir que les produits cartésiens sont répertoriés correctement.
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
Eh bien, une fois que vous êtes ici, le reste est facile. Extraire une combinaison unique du produit cartésien. Le point est, par exemple, lors de l'extraction de $ (1, 2) $, il suffit d'exclure $ (2, 1) $, donc pour une certaine combinaison comb, seuls ceux avec` comb == sort (comb) ʻ sont extraits. Faire.
python
template<typename T>
vector<vector<T>> combWithReplace(vector<T> choices, int n) {
vector<vector<T>> answer;
for (vector<T> comb: product(choices, n)) {
vector<T> toSorted = comb;
sort(toSorted.begin(), toSorted.end());
if (comb == toSorted) {
answer.push_back(comb);
}
}
return answer;
}
Maintenant, le programme pour énumérer les combinaisons en double est terminé. Enfin, encore une fois, essayez une énumération de combinaison pour autoriser les doublons de l'ensemble $ \ left \ {1, 2, 3 \ right \} $ et extraire les éléments $ 2 $.
python
int main(){
vector<int> choices = {1, 2, 3};
int n = 2;
vector<vector<int>> answer = combWithReplace(choices, n);
for (int i = 0; i < answer.size(); i++) {
cout << answer[i][0] << " " << answer[i][1] << endl;
}
}
Le résultat est le suivant. Vous pouvez voir que le même résultat que le calcul manuel est obtenu. Vous pouvez également voir que chaque combinaison est également triée.
1 1
1 2
1 3
2 2
2 3
3 3
En regardant le code source de Pythonʻitertools`, je n'ai jamais pensé que la mise en œuvre de C ++ serait aussi fastidieuse. Il y avait une raison pour laquelle la notation d'inclusion de liste existait même si elle était moins lisible. $ \ Ldots $. Si vous avez des erreurs, veuillez nous en informer. Merci d'avoir lu jusqu'au bout.
Ce qui suit est un exemple d'implémentation enseigné par @Nabetani. Veuillez consulter la section des commentaires pour les performances, etc.
Ma mise en œuvre est en ligne
{{}}
⇒{{1}, {2}, {3}}
⇒{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}
Alors que les éléments correspondants ont été extraits après avoir terminé le produit cartésien, dans cette implémentation, chaque combinaison est utilisée.
{} ⇒ {1} ⇒ {1, 1} ⇒ Ajouter à la réponse
⇒ {1, 2} ⇒ Ajouter à la réponse
⇒ {1, 3} ⇒ Ajouter à la réponse
{} ⇒ {2} ⇒ {2, 2} ⇒ Ajouter à la réponse
⇒ {2, 3} ⇒ Ajouter à la réponse $ \ cdots $
Il semble qu'il soit complété sous la forme et ajouté à la réponse. (Fonction ʻAppend () `dans la structure) Cela peut être plus facile à comprendre car il est similaire à l'opération d'énumération des combinaisons en double par calcul manuel.
c++14
#include <iterator>
#include <vector>
template <typename container_type>
std::vector<std::vector<typename container_type::value_type>>
combWithReplace(container_type const &choices, size_t n) {
using value_type = typename container_type::value_type;
using selected_t = std::vector<value_type>;
using itor_t = typename container_type::const_iterator;
struct impl { //La récursivité est gênante avec lambda, alors faites-en une classe
std::vector<std::vector<value_type>> &r_; //Avoir une référence pour éviter de copier
impl(std::vector<std::vector<value_type>> &r) : r_(r) {}
void append(selected_t &s, itor_t b, itor_t e, size_t n) {
if (n == 0) {
r_.push_back(s);
} else {
for (auto it = b; it != e; ++it) {
s.push_back(*it);
append(s, it, e, n - 1);
s.pop_back();
}
}
};
};
std::vector<std::vector<value_type>> r;
impl o{r};
selected_t e;
e.reserve(n);
o.append(e, std::cbegin(choices), std::cend(choices), n);
return r;
}
python3.8
def comb_with_replace(a, n):
r = []
def append(e, b, add_count):
"""Énumérer les éléments des combinaisons en double en utilisant récursif et ajouter les combinaisons trouvées à r
Parameters
----------
e : list
Combinaison en double au milieu de l'assemblage
b : int
Index au début des éléments disponibles
add_count : int
Nombre d'éléments à ajouter à e
"""
if add_count == 0:
r.append(e)
else:
for ix in range(b, len(a)):
append(e+[a[ix]], ix, add_count-1)
append([], 0, n)
return r
def main():
choices = [1, 2, 3]
for e in comb_with_replace(choices, 2):
print(e)
main()
Recommended Posts