Permutation (mögliche Kombinationen)

[juniorA]

Moin, moin,
Ich habe eine Menge von Teilen (max. 100 Stück), welche ich miteinander kombinieren will um zu testen ob bestimmte Kriterien eingehalten werden.
Wenn ich mich so richtig erinnere hat dieses etwas mit Permutationen zu tun.
Kennt einer einen brauchbaren Algorithmus, welcher alle möglichen Kombinationen ausgibt wenn N Werte zur Verfügung stehen. Wenn N z.B. 5 ist, sollen alle Kombinationen ausgegeben werden welche die Buchstaben ABCDE ergeben können.
In jeder Kombination darf ein Buchstabe nur einmal vorkommen.

[mkinzler]

http://www.schule-bw.de/unterricht/f...mbinatorik.pdf

[smallie]

Da gibt es n! Kombinationen.

Ich befürchte, daß mehr als n zwischen zehn und zwanzig aus Laufzeitgründen nicht mehr geht.

[gammatester]

Gibt's als Algorithmen bei Knuth.

Für Permutationen http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
und für Kombinationen http://www-cs-faculty.stanford.edu/~uno/fasc3a.ps.gz
oder für Klick-Klack-Techniker von http://rosettacode.org/wiki/Permutations#Delphi
bzw http://rosettacode.org/wiki/Combinations#Pascal

[Jens01]

@gammatester (bezieht sich auf die ersten beiden links)

[jobo]

Das ist vielleicht ein schönes Thema für SQL (Daten-Mengen), Kreuzprodukte, ..
Sobald man 2. Mengen vereint und keine geeigneten Join Kriterien festlegt, permutiert es quasi von allein.

[juniorA]

So richtig kann ich damit leider nichts anfangen.
Was ich suche ist eigentlich ein Generator der mir bei einer Vorgabe von n möglichen Eingangswerten alle möglichen Kombinationen dieser n Eingangswerte wiedergibt.
Maximal können dieses 99 Eingangswerte sein. Bis 11 Eingangswerte ging dieses gut, aber dann gab es dieses Problem.

[Dejan Vu]

Zitat von juniorA:

...alle möglichen Kombinationen...

Meinst Du Permutation, Kombination oder Variation oder einfach alle Zahlen zur Basis 'P'?
Was soll bei drei Eingabewerten herauskommen, die die Werte A, B oder C annehmen können?
Was erwartest Du eigentlich bei 99 Eingabewerten? Was machst Du mit den Ausgaben? Wie lange willst Du warten?

[Bjoerk]

Zitat von juniorA:

Bis 11 Eingangswerte ging dieses gut, aber dann gab es dieses Problem.

Müßte bis 12! gehen. Erst 13! ist größer MaxInt.

[Medium]

Bei n=99 wird es ein Ergebnis von rund 93326215443944152681699238856267000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000 Datensätzen geben (laut Windows Taschenrechner, und wenn ich bei den Nullen nicht 1-2 falsch gezählt habe - aber eh unwichtig). Wenn jedes der 99 Elemente ein Byte groß ist, wird das Ergebnis grob 84030901497958176291724381797125000000000000000000 00000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000 Terabyte umfassen. (Ebenfalls die gleiche Unsicherheit mit den Nullen, aber auch hier ziemlich egal.)

So.

Selbst wenn man es so machen würde, dass man nicht alle Ergebnise vorab speichert (was diverse Erden an Gesamtkapazität aller je gebauten Speichermedien konsumieren dürfte...), müsste man diese dennoch alle durchprüfen. Selbst wenn man dies jetzt bloß auf den Datendurchsatz aktuellen DDR3 RAMs berechnen würde, kann ich mir gut vorstellen, dass man das Endergebnis der Auswertung ungefähr kurz vor der Supernova unserer Sonne ablesen könnte. So ganz grob geschätzt.

Fazit: Entweder du kannst Einschränkungen machen, oder das Vorhaben ist von Anfang an komplett und vollständig, ohne Wenn und Aber, schlicht und ergreifend unmöglich. Ein Integer-Überlauf ist hier mit sicherheit das kleinste aller Probleme.