** Aktualisiert am 14.9.: Das im Kommentarbereich beschriebene Implementierungsbeispiel finden Sie am Ende dieses Artikels. (C ++, Python) **
Ich wollte eine Kombination erstellen, die eine Duplizierung in C ++ ermöglicht, an die ich nicht gewöhnt bin. Deshalb habe ich viel gesucht, aber ich konnte sie nicht leicht finden. Es gibt eine "Reihenfolge", die Duplikate zulässt, und eine Formel, die die Gesamtzahl der Duplikatkombinationen berechnet ($ \ small_n H_r $, die ich in der Junior High School gelernt habe), aber der Code, der Duplikatkombinationen aufzählen kann, wurde nicht umgedreht. Wenn ich es nachgeschlagen habe, scheint es, dass es in Python und so weiter normalerweise in "itertools" als Funktion namens "kombination_mit_replacement ()" enthalten ist, so dass Code (https://docs.python.org/ja/3/library/itertools.html) ) Und erneut in C ++ implementiert. Wenn Sie Fehler oder Verbesserungen haben, teilen Sie uns dies bitte mit.
Betrachten Sie zunächst als Beispiel eine Kombinationsaufzählung, wenn Sie $ 2 $ -Elemente aus der Menge $ \ left \ {1, 2, 3 \ right \} $ extrahieren, um eine Duplizierung zu ermöglichen. Der Ablauf selbst ist einfach und sieht folgendermaßen aus:
Mit anderen Worten, wenn Sie im Allgemeinen eine Duplizierung aus der Menge $ \ Omega $ zulassen und $ n $ Elemente extrahieren möchten, können Sie $ \ Omega $ in $ n $ duplizieren und eine eindeutige Kombination aus ihrem kartesischen Produkt extrahieren. Es wird sein.
Implementieren Sie zunächst das kartesische Produkt. Es scheint, dass es in Python auch eine Funktion namens "product ()" von "itertools" gibt, aber ich konnte die Doppellisten-Einschlussnotation im Quellcode nicht einholen, also habe ich das kartesische Produkt in Golang implementiert. Ich habe auf den Code der Person verwiesen, die ist (https://qiita.com/tesujiro/items/2e41e1159948dc90c3d9). Diese Person schreibt im Allgemeinen den Code, um das kartesische Produkt zwischen mehreren Sätzen von $ \ Omega_1, \ Omega_2, \ Omega_3, \ ldots $ zu berechnen.
In meiner Implementierung dieses Mal "Duplikate aus $ \ Omega $ zulassen und $ n $ Teile extrahieren", also $ \ Omega_1 = \ Omega, \ Omega_2 = \ Omega, \ Omega_3 = im Allgemeinen kartesisches Produkt Entspricht \ Omega, \ ldots, \ Omega_n = \ Omega $. Wenn der Wert von $ n $ zunimmt, wird es schwierig, $ \ Omega $ um die Anzahl von $ n $ zu duplizieren und dem Argument zuzuweisen, sodass $ n $ mit dem Argument repeat gezählt wird. Ich werde. Zunächst wird der Code unten veröffentlicht.
python
#include <bits/stdc++.h>
using namespace std;
template<typename T>
vector<vector<T>> productRecurse(vector<T>, int, vector<vector<T>>);
//kartesisches Produkt
template<typename T>
vector<vector<T>> product(vector<T> choices, int repeat) {
vector<vector<T>> emptyResult(1, vector<T>());//Leere Liste zum Speichern von Kombinationen
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;}//Geben Sie die Antwort zurück, wenn das kartesische Produkt fertig ist
vector<vector<T>> provisionalResult;//Kartesisches Produkt im Entstehungsprozess
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);
}
Betrachten wir zur Erläuterung des obigen Codes noch einmal ein Beispiel, um die Menge $ \ left \ {1, 2, 3 \ right \} $ in $ 2 $ zu duplizieren und ein kartesisches Produkt zu erstellen. Der Ablauf beim Aufrufen von "Produkt (Auswahl = {1, 2, 3}, Wiederholung = 2)" ist wie folgt.
productRecurse (Auswahl = {1, 2, 3}, Wiederholung = 2, Ergebnis = {{}}) wird aufgerufen.provisorisches Ergebnis = {{1}, {2}, {3}}.productRecurse (Auswahl = {1, 2, 3}, Wiederholung = 1, Ergebnis = {{1}, {2}, {3}}) wird aufgerufen.provisorisches Ergebnis = {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3 , 2}, {3, 3}} .productRecurse (Auswahl = {1, 2, 3}, Wiederholung = 0, Ergebnis = {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2 }, {2, 3}, {3, 1}, {3, 2}, {3, 3}}) wird aufgerufen.repeat == 0 ist das Argument result das endgültige kartesische Produkt.In Python bedeutet dies, dass der Teil, der in die Liste aufgenommen werden kann, rekursiv wiederholt wird. Lassen Sie es uns tatsächlich ausführen.
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;
}
}
Wie manuell berechnet, können Sie sehen, dass die kartesischen Produkte korrekt aufgelistet sind.
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
Nun, sobald Sie hier sind, ist der Rest einfach. Extrahieren Sie eine einzigartige Kombination aus dem kartesischen Produkt. Kurz gesagt, wenn Sie beispielsweise $ (1, 2) $ extrahieren, reicht es aus, $ (2, 1) $ auszuschließen. Für eine bestimmte Kombination "Kamm" werden also nur diejenigen mit "Kamm == sort (Kamm)" extrahiert. Machen.
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;
}
Jetzt ist das Programm zum Auflisten der doppelten Kombinationen abgeschlossen. Versuchen Sie abschließend erneut eine Kombinationsaufzählung, um Duplikate aus der Menge $ \ left \ {1, 2, 3 \ right \} $ zuzulassen und $ 2 $ -Elemente zu extrahieren.
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;
}
}
Das Ergebnis ist wie folgt. Sie können sehen, dass das gleiche Ergebnis wie bei der manuellen Berechnung erzielt wird. Sie können auch sehen, dass jede Kombination auch sortiert ist.
1 1
1 2
1 3
2 2
2 3
3 3
Beim Betrachten des Quellcodes für Pythonitertools hätte ich nie gedacht, dass die Implementierung von c ++ so mühsam sein würde. Es gab einen Grund, warum die Listeneinschlussnotation existierte, obwohl sie weniger lesbar war. $ \ Ldots $.
Wenn Sie Fehler haben, lassen Sie es uns bitte wissen. Vielen Dank für das Lesen bis zum Ende.
Das Folgende ist ein Implementierungsbeispiel, das von @Nabetani gelehrt wird. Bitte beachten Sie den Kommentarbereich für die Leistung usw.
Meine Implementierung steht im Einklang
{{}}
⇒{{1}, {2}, {3}}
⇒{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}
Während die entsprechenden Elemente nach Fertigstellung des kartesischen Produkts extrahiert wurden, wird in dieser Implementierung jede Kombination verwendet.
{} ⇒ {1} ⇒ {1, 1} ⇒ Zur Antwort hinzufügen
⇒ {1, 2} ⇒ Zur Antwort hinzufügen
⇒ {1, 3} ⇒ Zur Antwort hinzufügen
{} ⇒ {2} ⇒ {2, 2} ⇒ Zur Antwort hinzufügen
⇒ {2, 3} ⇒ Hinzufügen, um $ \ cdots $ zu beantworten
Es scheint, dass es in Form von vervollständigt und der Antwort hinzugefügt wird. (Append () Funktion in der Struktur)
Dies ist möglicherweise leichter zu verstehen, da es der Operation zum Aufzählen doppelter Kombinationen durch manuelle Berechnung ähnelt.
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 { //Rekursion ist mit Lambda problematisch, machen Sie es also zu einer Klasse
std::vector<std::vector<value_type>> &r_; //Haben Sie einen Verweis, um das Kopieren zu vermeiden
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):
"""Zählen Sie die Elemente doppelter Kombinationen mit rekursiv auf und fügen Sie die gefundenen Kombinationen zu r hinzu
Parameters
----------
e : list
Doppelte Kombination in der Mitte der Montage
b : int
Index am Anfang der verfügbaren Elemente
add_count : int
Anzahl der Elemente, die zu e hinzugefügt werden sollen
"""
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