Alle Kombinationen ausgeben

[Kegasetu]

Hallo zusammen,
ich bin mal wieder mit meinem Programm zugange... langsam habe ich kein Bock mehr :D

Das Problem habe ich schon in einem Vorheringen Thema angesprochen, nun will ich es auf eine andere Weise angehen.

Über ein Integer soll eingegeben werden, wie viel Stellen sich auf einen Bereich verteilen.

z.B. i :=5;
b :=20;

dann will ich alle Kombinationen bekommen, welche daraus entstehen.
Z.B. :- 1, 2, 3, 4, 5, x, x, x, x, x, x, x, x, x, x, x, x, x, ...
- 1, 2, 3, 4, x, 5, x, x, x, x, x, x, x, x, x, x, x, x, ...
- x, x, x, x, 1, 2, 3, 4, x, x, x, x, x, 5, x, x, x, x, ...

Auch kann es vorkommen, dass gezielt Stellen im Bereich nicht besetzt werden dürfen

Ich denke das Prinzip ist klar, wichtig ist, dass die 1 nicht hinter der 2 steht usw.
Das Forum hat bereits Ansätze für diese Problematik zu bieten, wie z. B. https://www.delphipraxis.net/158470-...gorithmus.html
https://www.delphipraxis.net/6804-ko...gs-zahlen.html

Aber daraus werde ich einfach nicht schlauer, meine Fähigkeiten der Informatik lassen sich als beschränkt adjektivieren.

Falls jemand vielleicht einen Lösunganstz für dieses Problem, wäre ich sehr dankbar wenn er sich meldet.

Danke für die Unterstützung, auch in den vorheringen Themen!

[Kegasetu]

Mein erster Gedankengang war alles in einem Array zu speichern

varation[] = (1,2,3,4,5,0,0,0,0,0,0,0,0)
und dieser würde seine Defintion dann anpassen.

Ich bin davon überzeugt das es so gehen würde, aber ich komme einfach nicht drauf wie ich hier sinnvoll durchzählen kann.

[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

[Kegasetu]

Zitat:

Zitat von Michael II (Beitrag 1477012)

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 (oder wenn du willst auch alle) Lösung 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.

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

Probier's mal aus...

Gruss
M

Danke für den Code, aber ich komme nicht so ganz damit klar...

Ich würde jetzt gerne die Stelle aufzeigen, aber es sind so viele.

Was beduetet z.B. record? Oder wie genau funktionert das:

Delphi-Quellcode:

 TRes = record
      br : TBrett;
      bew : TBewertungstyp;
     end;

Ich habe schon den Anspruch zu verstehen was ich da mache aber so ganz tief bin ich nicht in der Materie. Ich versuche es so einfach wie möglich zu machen, damit ich immer erklären kann was da passiert. Und die Hoffung des es irgendwie mit einem simplen Array funktionert ist nach wie vor da :D

Hier mal meine Überlegung, die so noch nicht funktionert:

Delphi-Quellcode:

var i, q, durch : integer;
variation [0..200]: Array of Integer;   //Array definieren, maximaler Bereich von 200

begin

for i:= 0 to strtoint(edit1.Text) do  // Anzahl der Halterungen
 variation [i] := i;                  //Hier das Array füllen 


for q:= strtoint(edit1.Text) to strtoint(edit2.Text) do     //Hier wird die Bereichgröße (edit2) eingegeben (später ist das in der Rechnung integriert und richtet sich nach der Länge des Balkens)
 begin
   variation [strtoint(edit1.Text)] := variation [strtoint(edit1.Text)+q]  //der Letzte Wert wird hochgezählt und dann ausporbiert.Hier bin ich momentan und komme nicht weiter. Die Vorgehensweise ist auch falsch. 
 end;  
end;

Um es Verbal zu beschreiben , in der zweiten for Schleife sollen dann alle Kombinationen erstellt und im Anschluss ausprobiert werden.

[Michael II]

Die beschriebene Rekursion findest du in

Delphi-Quellcode:

function bewerte( brett : TBrett ; n, k : integer ) : TRes;

Du kannst ja mal im Debugger einen Breakpoint setzen am Anfang der Funktion und dann durchsteppen, damit du in etwa siehst was abläuft.

Jedes Mal, wenn in bewerte eine neue Kombination gefunden worden ist wird

Delphi-Quellcode:

function meingebewertungsfunktion( brett : TBrett) : TRes;

aufgerufen. In dieser Funktion nimmst du die Bewertung vor. Die gefundene Kombination findest du im Array brett.wo.

Du fragst, was ein record ist - da liest du am besten kurz im Hilfe zu Delphi. Im Wesentlichen ist es eine Zusammenfassung von Variablen.

Zitat:

Und die Hoffung des es irgendwie mit einem simplen Array funktionert ist nach wie vor da

Genau diesen simplen Array hast du in brett.wo.

[Kegasetu]

Zitat:

Zitat von Michael II (Beitrag 1477030)

Die beschriebene Rekursion findest du in

Delphi-Quellcode:

function bewerte( brett : TBrett ; n, k : integer ) : TRes;

Du kannst ja mal im Debugger einen Breakpoint setzen am Anfang der Funktion und dann durchsteppen, damit du in etwa siehst was abläuft.

Jedes Mal, wenn in bewerte eine neue Kombination gefunden worden ist wird

Delphi-Quellcode:

function meingebewertungsfunktion( brett : TBrett) : TRes;

aufgerufen. In dieser Funktion nimmst du die Bewertung vor. Die gefundene Kombination findest du im Array brett.wo.

Du fragst, was ein record ist - da liest du am besten kurz im Hilfe zu Delphi. Im Wesentlichen ist es eine Zusammenfassung von Variablen.

Zitat:

Und die Hoffung des es irgendwie mit einem simplen Array funktionert ist nach wie vor da

Genau diesen simplen Array hast du in brett.wo.

Hättest du vielleicht ein Beispiel mit 5 Halterungen und 20 Plätzen? Und als Ausgabe dann eine simple showMessage mit den Werten

[Andreas13]

Zitat:

Zitat von Kegasetu (Beitrag 1477016)

Was beduetet z.B. record? Oder wie genau funktionert das:

Delphi-Quellcode:

 TRes = record
      br : TBrett;
      bew : TBewertungstyp;
     end;

Ich habe schon den Anspruch zu verstehen was ich da mache aber so ganz tief bin ich nicht in der Materie. Ich versuche es so einfach wie möglich zu machen, damit ich immer erklären kann was da passiert. Und die Hoffung des es irgendwie mit einem simplen Array funktionert ist nach wie vor da :D

Du solltest Dich zuerst mit den Grundlagen von Delphi beschäftigen: Die neuste Version von Delphi-Starter findest Du im Forum Delphi-Treff https://www.delphi-treff.de/downloads/e-book/. Das ist eine gute und kostenfreie Einführung in die Delphi-Basics.
Gruß, Andreas

[Andreas13]

Zum Programmieren braucht man zahlreiche getestete Algorithmen. Ein gutes einführendes Buch mit Pascal-Code findest Du kostengünstig z.B. hier:
1):
Robert Sedgewick: Algorithmen. Addison-Wesley Verlag: (1992)...(2001)
https://www.zvab.com/servlet/BookDet...-srp1-_-title1
2):
Es gibt auch eine neuere Auflage aus dem Jahr 2014, die Codebeispiele sind aber in Java und nicht mehr in Pascal.
Robert Sedgewick und Kevin Wayne: Algorithmen: Algorithmen und Datenstrukturen (Pearson Studium - IT) Taschenbuch (2014)
https://www.amazon.de/Algorithmen-Da...5017380&sr=8-2
Es gibt noch zig weitere empfehlenswerte Werke über diverse mathematische & numerische Algorithmen, aber für den Anfang würde es Dir absolut reichen, damit Du etwas Orientierung und Halt findest und effizienter arbeiten kannst.
Gruß, Andreas

[Kegasetu]

Zitat:

Zitat von Andreas13 (Beitrag 1477038)

Du solltest Dich zuerst mit den Grundlagen von Delphi beschäftigen: Die neuste Version von Delphi-Starter findest Du im Forum Delphi-Treff https://www.delphi-treff.de/downloads/e-book/. Das ist eine gute und kostenfreie Einführung in die Delphi-Basics.
Gruß, Andreas

Besser wäre es, aber ich muss wirklich nur dieses Programm fertig bekommen. Danach werde ich vermutlich nie wieder Kontakt zu Delphi haben, obwohl es schon einige Vorzüge mit sich bringt.

[Andreas13]

Geht es immer noch um das Projekt mit den linearen Gleichungssystemen?