Alle Kombinationen ausgeben

[Michael II]

Hallo K

in https://www.delphipraxis.net/1476191-post36.html

habe ich dir gezeigt wie du ohne tief greifende Kombinatorik alle möglichen Kombinationen durchlaufen kannst und dabei gleich noch eine beste Lösung (oder wenn du willst auch alle besten Lösungen) finden kannst.

Du kannst das rekursiv tun. Nimm an, du hast n Positionen und k Dinge die du reinhängen willst.
Du gehst alle möglichen (Brett-)Positionen von links nach rechts durch. Bei jeder Position gibt es genau zwei Möglichkeiten: Du machst entweder nix oder du hängst was rein. Du gehst eine Position weiter - und wieder das gleiche Spiel: nix tun oder was tun. und so weiter...

Wann brichst du ab? Es gibt zwei Abbruchkriterien:
Fall 1: Sobald du k Mal was getan hast bist du fertig und bewertest diese Kombination.
Fall 2: Du brichst ab sobald du weisst, dass du noch i Mal was tun müsstest, aber nur noch p<i Positionen frei sind. (Beispiel n=10, k=5, wir stehen bei Position 8 (haben also noch 8 9 10 frei) und haben erst an einer Position (1-7) was getan. Wir müssten also (da k=5) noch vier Mal was tun, haben aber nur noch drei mögliche Positionen (8 9 10) => Geht nicht; Abbruch)

Natürlich gibt es schönere Wege alle Kombinationen aufzuzählen. Aber dieser Weg ist für dich sicher nachvollziehbar.

Probier's mal aus...

Zusatz: Du schreibst, dass gewisse Kombinationen u.U. nicht erlaubt sind. Da unsere Rekursion alle möglichen Kombinationen aufzählt, kannst du eine unerlaubte k sehr einfach via Bewertungsfunktion filtern indem du k mit 0 bewertest. (Wenn du mit riesig grossen n's arbeiten würdest: Du könntest auch direkt in der Rekursion filtern und hättest dadurch bessere Performance. Negativ: Der Code wird rasch unübersichtlich.)

Gruss
M