Permutation (mögliche Kombinationen)

[juniorA]

Ist einleuchtend.
Danke für die Antwort.
Vielleicht gibt es nächsten Jahrtausend eine Antwort darauf.

Zwischenspeichern muss ich übrigens immer nur eine Variante (Kombination), da ich mit jeder Ausgabe einer Kombination teste ob sie bestimmte Kriterien erfüllt. Die Variante (Reihenfolge der Werte) die am dichtesten am Ziel liegt wird sich gemerkt.
Wenn eine bessre gefunden ist, wird die alte überschrieben.

[p80286]

Das erinnert mich irgendwie an affen und Schreibmaschinen

Gruß
K-H

[Sir Rufo]

Zitat von juniorA:

Ist einleuchtend.
Danke für die Antwort.
Vielleicht gibt es nächsten Jahrtausend eine Antwort darauf.

Zwischenspeichern muss ich übrigens immer nur eine Variante (Kombination), da ich mit jeder Ausgabe einer Kombination teste ob sie bestimmte Kriterien erfüllt. Die Variante (Reihenfolge der Werte) die am dichtesten am Ziel liegt wird sich gemerkt.
Wenn eine bessre gefunden ist, wird die alte überschrieben.

Dann machen wir mal ein wenig Robert Lemke, wenn du uns die Informationen so nicht geben möchtest

Gehe ich recht in der Annahme, dass jedes Element in einer Kombination nur einmal auftauchen darf?

Code:

Menge (1,2,3,4)
gültig sind (1,2), (1,3), (1,2,3)
ungültig sind (1,1), (1,2,2)

Wenn du die beste Kombination haben möchtest, warum willst du dann erst alle Kombinationen zusammenbauen?
Wenn (1,2) die Kriterien nicht erfüllt und man weiß, dass diese Kombination auch nicht besser wird, wenn die mit einem anderen Element kombiniert wird, dann kann man diese Kombinationen schon mal komplett ausnehmen und spart sich eine Menge weiterer Prüfungen.

[Dejan Vu]

Das nennt sich 'pruning', das der Traversierungsbaum beschnitten (engl: to prune) wird. Wenn man z.B. weiß, das (1,2) vollkommener Schrott ist und auch (1,2,x,y,z...) dann kann man getrost alle Derivate ignorieren. So wird in der klassischen Spieletheorie der Suchbaum (Schach z.B.) drastisch verkürzt.

Aber da der Fragesteller wohl selbst nicht weiß, was er will und Fragen nicht beantworten kann, soll er halt weiter friemeln.

[BUG]

Vielleicht braucht man ja auch nicht suchen, sondern kann das Ergebnis konstruieren. Wer weiß?
Ohne ein wenig Details zu Bedingungen kann man noch nicht mal versuchen, eine ordentliche Vermutung anstellen.

Wenn du wirklich nichts verraten willst oder das Problem zu kompliziert ist und das Problem nicht unbedingt mit Delphi lösen musst, kannst du dir mal Prolog (oder Verwandte davon) angucken. Die gängigen Prolog-Solver sollten bedeutend besser sein als alles, was man mal eben so zusammen schustert.

[Dejan Vu]

Zitat von BUG:

Die gängigen Prolog-Solver sollten bedeutend besser sein als alles, was man mal eben so zusammen schustert.

NP-Komplett bleibt NP-Komplett, egal in welcher Sprache. Sofern Du in Prolog keine Optimierungen (pruning) formulierst, wirst Du genauso lange warten.

Da Rekursion einer der zentralen Deklarationsmetapher von Prolog ist, dürfte die Implementierung auch alles andere als Obersuperoptimal sein, obwohl ein Prolog-Interpreter tail recursion iterativ auflösen sollte.

Prolog wird teilweise bei Expertensystemen eingesetzt, sodass man hier prüfen müsste, inwieweit der TE ein derartiges System benötigt.

[BUG]

Zitat von Dejan Vu:

NP-Komplett bleibt NP-Komplett, egal in welcher Sprache. Sofern Du in Prolog keine Optimierungen (pruning) formulierst, wirst Du genauso lange warten.

Stimmt, ich war ein bisschen verwirrt

[Dejan Vu]

Zitat von BUG:

Stimmt, ich war ein bisschen verwirrt

Kein Wunder, bei dem Thread

[juniorA]

Zu Beitrag 17
Nein ganz so einfach ist dieses nicht.
Ich habe maximal 99 Teillängen. Diese will ich auf Paletten legen die eine Länge von 12 Metern haben. Mir geht es jetzt darum, dass ich diese Teile so kombiniere, dass ich möglichst wenige Paletten brauche. Hinzu kommt noch folgende Schwierigkeit dass ich in der Mitte eines Abstellung habe wo das letzte Teil von der 1. Hälfte der Belegung maximal um 40 cm überstehen darf. Teile, deren Länge > 6.4 m sind, fallen von vorne sowieso raus.

[Dejan Vu]

0/1-Knapsack-Problem. NP-Komplett. Kannste nicht durchprobieren. Aber Gott-Sei-Dank kann man das wohl mit linearer Programmierung lösen (wenn die Werte ganzzahlig sind).