C++ iterativer Algorithmus für das generieren von Kombinationen

Hey!

Kenne mich mit C++ und dessen Libraries nicht wirklich aus, aber.. muss es denn wirklich iterativ sein? Rekursiv wäre das wohl einfach und elegant zu lösen.

Ansonsten schau dir mal http://stackoverflow.com/questions/1277…elements-from-n (und dort bei der ersten Antwort "Chase's Twiddle" an) - ist wohl das was du suchst

Bin mir auch nicht sicher, ob ich dein Problem richtig verstanden, denn folgende beiden Punkte verstehe ich offen gestanden nicht:

• Du hast für 26 Buchstaben _alle_ Permutationen berechnen lassen? Kann ich mir nicht vorstellen.. das wären 26! = 403.291.461.126.605.635.584.000.000 Kombinationen. Selbst bei 100 Milliarden Kombinationen pro Sekunde würde das 127882883 Jahre dauern.
• Warum genau überprüfst du bei einer Permutation, ob ein Element in den ersten k Elementen doppelt Auftritt. Kann bei einer Permutation eigentlich nicht sein, siehe http://www.cplusplus.com/reference/algo…xt_permutation/

l.g.

Zitat von henriknikolas

Chase's twiddle hört sich gut an. Ich habe zum testen die Menge meiner Buchstaben erstmal auf 10 reduziert. Dann hat es etwa 30 s gedauert alle Variationen auszurechnen. Ich hatte mich nämlich verschrieben, ich meinte Variationen und nicht Kombinationen. Deshalb muss ich auch prüfen ob bei einer Permutation ein Element doppelt auftritt:
aaaaaaaaaa ist eine korrekte Permutation aber keine könn korrekte Variationen, da das a mehr als einmal auftritt.

Schön, dass das für dich zu passen scheint.

Mit deiner Aussage zu deinem ursprünglichen Algorithmus hast du mich jetzt aber verwirrt: Du hast 10 Buchstaben in deiner Menge. Von diesen 10 Buchstaben hast du dir alle Permutationen in einer Schleife mit "next_permuation_ erzeugt (letters = {'a','b','c','d','e','f','g','h','i','j'}; next_permutation(letters, letters+10); oder so), von jeder Permutation die ersten k Elemente genommen und geschaut ob bei diesen k Elementen doppelte Elemente vorkommen. Falls nicht, hast du sie ausgegeben/gespeichert?

Falls ja:

next_permutation ist Permutation ohne Wiederholung - aaaaaaaaaa kann nicht entstehen, da next_permutation die lexikografisch nächst höhere Permutation zurück gibt(steht auch N! dort und nicht N^N, wie es bei Permutation mit Zurücklegen sein müsste):

Zitat von http://www.cplusplus.com/reference/algorithm/next_permutation/

"A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range)."
[..]
"Rearranges the elements in the range [first,last) into the next lexicographically greater permutation."

Schau dir das Beispiel mit den Faktoriellen unten an. Dort kommt beispielsweise auch nicht [1,1,1] vor.

Was du allerdings tun hättest müssen, ist dir anzuschauen, ob die ersten k Elemente gleich wie die ersten k Elemente einer anderen Permutation sind. Die Permutationen abcdefghji und abcdefgjhi sind zwar verschieden, aber für k = 7 zum Beispiel hat man abcdefg und abcdefg - es würden doppelte Ausgaben entstehen.

Falls nein: Bin doof, sry