AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Permutation (mögliche Kombinationen)
Thema durchsuchen
Ansicht
Themen-Optionen

Permutation (mögliche Kombinationen)

Ein Thema von juniorA · begonnen am 16. Jun 2014 · letzter Beitrag vom 20. Jun 2014
Antwort Antwort
Seite 1 von 2  1 2      
juniorA

Registriert seit: 14. Sep 2011
112 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#1

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 17:13
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.
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#2

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 17:20
Das erinnert mich irgendwie an affen und Schreibmaschinen

Gruß
K-H
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#3

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 17:41
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.
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#4

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 18:46
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.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#5

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 20:11
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.
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#6

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 20:25
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.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#7

AW: Permutation (mögliche Kombinationen)

  Alt 17. Jun 2014, 22:12
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
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#8

AW: Permutation (mögliche Kombinationen)

  Alt 18. Jun 2014, 05:53
Stimmt, ich war ein bisschen verwirrt
Kein Wunder, bei dem Thread
  Mit Zitat antworten Zitat
juniorA

Registriert seit: 14. Sep 2011
112 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#9

AW: Permutation (mögliche Kombinationen)

  Alt 19. Jun 2014, 13:47
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.

  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#10

AW: Permutation (mögliche Kombinationen)

  Alt 19. Jun 2014, 15:38
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).

Geändert von Dejan Vu (19. Jun 2014 um 15:40 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:14 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz