|
|
Forum: PC-Programmierung Algorithmus zur Auswahl n aus m mit WiederholungHallo, kann mir jemand mal kurz helfen dazu. Ich habe m Zeichen und möchte daraus alle möglichen j Kombinationen von n Zeichen generieren (n < m) wobei die Zeichen in n alle ein- bis n mal vorkommen können (d.h. Wiederholung ist möglich). Die Reihenfolge der Zeichen in der Kombination soll keine Rolle spielen. C++ und standard lib bevorzugt.
Danke. https://de.wikipedia.org/wiki/Kombination_(Kombinatorik) j = (n+m-1)! / ((n-1)! * m!) und wenn du keine for-loop mehr hin bekommst ... tgamma = (i+1)! https://stackoverflow.com/questions/50132863/is-there-any-built-in-factorial-function-in-c/50134255 math.h https://en.cppreference.com/w/c/numeric/math/tgamma :
Bearbeitet durch User
> Algorithmus zur Auswahl n aus m mit Wiederholung In allen Sprachen: https://rosettacode.org/wiki/Combinations_with_repetitions
Beitrag #7319904 wurde vom Autor gelöscht.
schon spät heute, hab's zur Übung nur schnell ins Python gehackt. Umsetzung in C++ mit stdlib wäre dann analog. Vielleicht würde man sich noch mehr Gedanken drüber machen, welche arrays wirklich wie oft erzeugt werden müssen.
output:
Wenn man genug Speicher hat für den m^n Lösungsraum ist es sicherlich effizienter, einfach erst alle m^n Lösungen mit BFS aufzulisten und dann am Ende einen Durchlauf zu machen, bei dem alles reihenfolgeninvariant gehasht wird. Das wäre dann O(m^n) So ist aber die Komplexität O(m^n n log(n)) Dafür könnte man viel Herzblut die Sortierung aber vielleicht inkrementell mit insert-sort beschleunigen, da ja immer nur ein Element eingefügt wird. Diese Frage ist ja prädestiniert für ChatGTP ;-)
Antwort auf die kopierte Frage des TO:
Eine Möglichkeit, dies in C++ mit der Standard-Bibliothek zu tun, ist
die Verwendung der next_permutation() Funktion aus der <algorithm>
Bibliothek. Sie können zunächst eine Permutation aller Zeichen in m
erstellen und dann next_permutation() in einer Schleife aufrufen, um
alle möglichen Permutationen zu generieren. Um die Anzahl der Zeichen in
der Kombination auf n zu beschränken, können Sie die ersten n Zeichen
der aktuellen Permutation verwenden. Hier ist ein Beispiel-Code:
#include <iostream>
#include <algorithm>
int main() {
std::string m = "abc";
int n = 2;
// Erstellen Sie eine Permutation aller Zeichen in m
std::sort(m.begin(), m.end());
int j = 0;
do {
// Verwenden Sie die ersten n Zeichen der aktuellen Permutation
std::cout << "j" << j << ": ";
for (int i = 0; i < n; i++) {
std::cout << m[i];
}
std::cout << std::endl;
j++;
} while (std::next_permutation(m.begin(), m.end()));
return 0;
}
Beachten Sie, dass die obige Lösung die Reihenfolge der Zeichen in der
Kombination nicht berücksichtigt, sondern lediglich die Anzahl der
Zeichen beschränkt. Wenn die Reihenfolge der Zeichen wichtig ist,
müssten Sie eine andere Lösung verwenden.
Angehängte Dateien:
kompiliert. tut aber nicht was es soll. fairerweise steht das ja auch im disclaimer, der ausgespuckt wurde. :
Bearbeitet durch User
Beitrag #7320065 wurde vom Autor gelöscht.
A. S. schrieb: > kompiliert. tut aber nicht was es soll. Vielleicht hätte TO in der Beispielsequenz noch ba, ca und cb dazuschreiben sollen. Im Beispiel ist n 1,2 - man könnte aber auch 0,1,2 denken. So ein wenig guckt hier auch die Frage nach dem Compiler um die Ecke. Darüberhinaus kann man die Anzahl der möglichen Kombinationen berechnen und die Ausgabe überprüfen. Das heißt also: wenn die Frage uneindeutig ist, kann die KI zumindest helfen, eindeutiger zu fragen. Zum Beispiel bei den Project Euler net Fragen könnte es hilfreich sein, was einer KI zu den Fragen da "einfällt". (https://projecteuler.net/archives) ich versteh gerade nicht, was das problem bei der Fragestellung ist der will "n aus m" auswählen mit Zurücklegen (Lösungsraum m^n) und dabei soll die Reihenfolge im Ergebnis irrelevant sein (Lösungsraum nochmal reduziert). Dann sollen alle möglichen Lösungen aufgelistet werden. Zur Erklärung ist da ein Beispiel. Die Lösung von chatgpt ist ohne Zurücklegen aber mit Reihenfolge in der Lösung. :
Bearbeitet durch User
heute mit klarem Kopf nochmal eine einfachere Lösung, die auch deutlich leichter in C++ zu übertragen ist und komplett ohne sortieren oder hashing auskommt. Aber: es darf keine duplikate in m geben!
A. S. schrieb: > kompiliert. tut aber nicht was es soll. Ist wohl typisch ChatGPT. In einem anderen Thread wurde ein ChatGPT-Programm veröffentlicht zum Auslesen von Daten einer Uhr - bloss dummerweise nicht für den angefragten Uhren-IC verwendbar. Anscheinend wird aus dem Fundus etwas geholt, das ein ähnliches Problem behandelt, aber ob die Lösung für den konkreten Fall anwendbar ist ist der KI schnurzegal. Ein Verständnis des Problems ist nicht vorhanden. Georg Georg M. schrieb: >> Algorithmus zur Auswahl n aus m mit Wiederholung > > In allen Sprachen: > https://rosettacode.org/wiki/Combinations_with_repetitions Hallo danke für den Link, das ist genau das was ich gesucht habe. Ich wollte schon die einzelnen Kombinationen und nicht nur die Anzahl. Auch für den Tip von Apollo M. bzgl. tgamma für die Fakultätsberechnung, das war mir auch noch nicht bekannt. Eure Antworten zeigen auch daß meine Frage von menschlicher Intelligenz eher richtig und von ChatGP falsche beantwortet wurde :) Hans H. schrieb: > Eure Antworten zeigen auch daß meine Frage von menschlicher Intelligenz > eher richtig und von ChatGP falsche beantwortet wurde :) Sonst könnte man das Forum ja auch schliessen. Obwohl, was ChatGPT sicher perfekt produzieren würde wären die üblichen Pöbeleien, und die machen ja inzwischen den Hauptanteil aus. Vielleicht kriegen die Betreiber es ja hin, 2 oder mehr KI-Instanzen gegeneinander zu hetzen, dann bräuchte man garkeine User mehr. Aber nach einiger Zeit würden die Werbekunden das sicher merken wenn nichts mehr verkauft wird. Georg Auf stackoverflow haben se chatGPT Antworten bereits gesperrt. Zu schlecht, häufig komplett falsch Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.
|
|
Thread beobachten
Seitenaufteilung abschalten