Algorithmus zur Auswahl n aus m mit Wiederholung

[Hans H. (loetkolben)]

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.

Beispiel m= "abc"
n= 2
j0 "aa"
j1 "bb"
j2 "cc"
j3 "ab"
j4 "bc"
j5 "ac"

Danke.

[Apollo M. (Firma: @home) (majortom)]

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

[Georg M. (g_m)]

> Algorithmus zur Auswahl n aus m mit Wiederholung

In allen Sprachen:
https://rosettacode.org/wiki/Combinations_with_repetitions

[A. S. (rava)]

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.

def _generate_permutations(m, n):
    substrings = _generate_permutations(m, n-1) if n > 2 else m
    
    results = set()  # hash-based set of strings
    for remainder in substrings:
        for letter in m:
            candidate = remainder + letter  # new string
            candidate_sorted = "".join(sorted(remainder + letter))  # sort new string
            results.add(candidate_sorted)
    return results

for perm in sorted(_generate_permutations(m="abc", n=2)):
    print(perm)

output:

aa
ab
ac
bb
bc
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.

[Andreas B. (bitverdreher)]

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. (rava)]

kompiliert. tut aber nicht was es soll.

fairerweise steht das ja auch im disclaimer, der ausgespuckt wurde.

[rbx (Gast)]

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)

[A. S. (rava)]

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.

[A. S. (rava)]

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!

def _generate_permutations(m, n):
    results = []
    for idx, letter in enumerate(m):
        sub_alphabet = m[idx:]
        substrings = _generate_permutations(sub_alphabet , n-1) if n > 2 else sub_alphabet 
        for remainder in substrings:
            results.append(remainder + letter)
    return results

results = _generate_permutations(m="abc", n=2)
for perm in sorted(results):
    print(perm)

[Georg (Gast)]

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

[Hans H. (loetkolben)]

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 :)

[Georg (Gast)]

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

[Da Baby (Gast)]

Auf stackoverflow haben se chatGPT Antworten bereits gesperrt.
Zu schlecht, häufig komplett falsch