Forum: PC-Programmierung Algorithmus zur Auswahl n aus m mit Wiederholung


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Hans H. (loetkolben)


Lesenswert?

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.
1
Beispiel m= "abc"
2
n= 2
3
j0 "aa"
4
j1 "bb"
5
j2 "cc"
6
j3 "ab"
7
j4 "bc"
8
j5 "ac"

Danke.

von Apollo M. (Firma: @home) (majortom)


Lesenswert?


: Bearbeitet durch User
von Georg M. (g_m)


Lesenswert?

> 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.
von A. S. (rava)


Lesenswert?

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.

von Andreas B. (bitverdreher)


Lesenswert?

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.

von A. S. (rava)


Angehängte Dateien:

Lesenswert?

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.
von rbx (Gast)


Lesenswert?

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)

von A. S. (rava)


Lesenswert?

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
von A. S. (rava)


Lesenswert?

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)

von Georg (Gast)


Lesenswert?

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

von Hans H. (loetkolben)


Lesenswert?

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

von Georg (Gast)


Lesenswert?

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

von Da Baby (Gast)


Lesenswert?

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

Antwort schreiben

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

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.