Algorithmus zur Auswahl n aus m mit Wiederholung

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

Algorithmus zur Auswahl n aus m mit Wiederholung

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

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;

1

// Erstellen Sie eine Permutation aller Zeichen in m

2

std::sort(m.begin(), m.end());

3

4

int j = 0;

5

do {

6

    // Verwenden Sie die ersten n Zeichen der aktuellen Permutation

7

    std::cout << "j" << j << ": ";

8

    for (int i = 0; i < n; i++) {

9

        std::cout << m[i];

10

    }

11

    std::cout << std::endl;

12

    j++;

13

} while (std::next_permutation(m.begin(), m.end()));

14

15

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.

kompiliert. tut aber nicht was es soll.

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

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 

6

        for remainder in substrings:

7

            results.append(remainder + letter)

8

    return results

9

10

results = _generate_permutations(m="abc", n=2)

11

for perm in sorted(results):

12

    print(perm)

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