Hallo,
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.
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.
1
def _generate_permutations(m, n):
2
substrings = _generate_permutations(m, n-1) if n > 2 else m
3
4
results = set() # hash-based set of strings
5
for remainder in substrings:
6
for letter in m:
7
candidate = remainder + letter # new string
8
candidate_sorted = "".join(sorted(remainder + letter)) # sort new string
9
results.add(candidate_sorted)
10
return results
11
12
for perm in sorted(_generate_permutations(m="abc", n=2)):
13
print(perm)
output:
1
aa
2
ab
3
ac
4
bb
5
bc
6
cc
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.
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.
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!
1
def _generate_permutations(m, n):
2
results = []
3
for idx, letter in enumerate(m):
4
sub_alphabet = m[idx:]
5
substrings = _generate_permutations(sub_alphabet , n-1) if n > 2 else sub_alphabet
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
Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.
Wichtige Regeln - erst lesen, dann posten!
Groß- und Kleinschreibung verwenden
Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang