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?

[Kegasetu]

Zitat:

Zitat von Andreas13 (Beitrag 1477048)

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

ja, aber das habe ich in den Griff bekommen. Zumindest mit der von mir gewählten Vorgehensweise.

[Andreas13]

Zitat:

Zitat von Kegasetu (Beitrag 1476997)

Ü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.

Sorry, aber ich habe nicht ganz verstanden, was Du genau vorhast.

[TiGü]

Zitat:

Zitat von Andreas13 (Beitrag 1477038)

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.

Bei mir ist der Link schon seit Monaten tot, da kommt keine PDF mehr.

[Michael II]

Zitat:

Zitat von Kegasetu (Beitrag 1477031)

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

Das Beispiel (siehe Link von oben) arbeitet mit 4 Halterungen und 10 Plätzen. Du kannst das leicht anpassen. Spiel's doch mal mit den 4 aus 10 durch. Du musst vorher nur noch in der Bewertungsfunktion meingebewertungsfunktion festlegen welche Kombination gut für dich ist und welche nicht. Danach lässt du das Programm laufen und eine beste Lösung wird berechnet.

[Andreas13]

Zitat:

Zitat von TiGü (Beitrag 1477052)

Zitat:

Zitat von Andreas13 (Beitrag 1477038)

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.

Bei mir ist der Link schon seit Monaten tot, da kommt keine PDF mehr.

Komisch... Aber ich habe den Delphi-Starter im Webarchiv gefunden:
http://web-old.archive.org/web/20120...nloads/e-book/
Gruß, Andreas

[Kegasetu]

Zitat:

Zitat von Michael II (Beitrag 1477053)

Zitat:

Zitat von Kegasetu (Beitrag 1477031)

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

Das Beispiel (siehe Link von oben) arbeitet mit 4 Halterungen und 10 Plätzen. Du kannst das leicht anpassen. Spiel's doch mal mit den 4 aus 10 durch. Du musst vorher nur noch in der Bewertungsfunktion meingebewertungsfunktion festlegen welche Kombination gut für dich ist und welche nicht. Danach lässt du das Programm laufen und eine beste Lösung wird berechnet.

Okay, ich probiere es morgen mal durch.

Eine Frage noch, wie wird das ganze getartet? Ich benutzte normalerweise nur eine Button.

[Kegasetu]

Zitat:

Zitat von Kegasetu (Beitrag 1477071)

Eine Frage noch, wie wird das ganze getartet? Ich benutzte normalerweise nur eine Button.

Mein Fehler, weiter unten steht es.

[Kegasetu]

Zitat:

Zitat von Michael II (Beitrag 1477053)

Zitat:

Zitat von Kegasetu (Beitrag 1477031)

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

Das Beispiel (siehe Link von oben) arbeitet mit 4 Halterungen und 10 Plätzen. Du kannst das leicht anpassen. Spiel's doch mal mit den 4 aus 10 durch. Du musst vorher nur noch in der Bewertungsfunktion meingebewertungsfunktion festlegen welche Kombination gut für dich ist und welche nicht. Danach lässt du das Programm laufen und eine beste Lösung wird berechnet.

Der Code funktioniert so weit. Nun bekomme ich aber das Problem, wenn ich mehr als 13 Stellen am Brett habe bekomme ich den Fehler: stack overflow

Es sollte schon möglich sein so um die 200 Stellen besetzten zu können.

[Kegasetu]

Zitat:

Zitat von Kegasetu (Beitrag 1477088)

Zitat:

Zitat von Michael II (Beitrag 1477053)

Zitat:

Zitat von Kegasetu (Beitrag 1477031)

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

Das Beispiel (siehe Link von oben) arbeitet mit 4 Halterungen und 10 Plätzen. Du kannst das leicht anpassen. Spiel's doch mal mit den 4 aus 10 durch. Du musst vorher nur noch in der Bewertungsfunktion meingebewertungsfunktion festlegen welche Kombination gut für dich ist und welche nicht. Danach lässt du das Programm laufen und eine beste Lösung wird berechnet.

Der Code funktioniert so weit. Nun bekomme ich aber das Problem, wenn ich mehr als 13 Stellen am Brett habe bekomme ich den Fehler: stack overflow

Es sollte schon möglich sein so um die 200 Stellen besetzten zu können.

Das Problem hat sich auch geklärt. Ich werde mich jetzt mal ransetzten alles zusammen zuwürfeln.

[Michael II]

Zitat:

Zitat von Kegasetu (Beitrag 1477088)

Der Code funktioniert so weit. Nun bekomme ich aber das Problem, wenn ich mehr als 13 Stellen am Brett habe bekomme ich den Fehler: stack overflow

Es sollte schon möglich sein so um die 200 Stellen besetzten zu können.

Wie du später gemerkt hast, gibt's keinen Stack Overflow.

Wenn du aber echt mit 200 Stellen rechnen lassen willst, dann musst du dir bewusst sein, dass das Aufzählen aller möglichen Kombinationen länger dauern kann als wir alle warten können. Beispiel n=200 Stellen und an k=100 Stellen was reinhängen: 9.054851465610329e+58 mögliche Kombinationen.
(Alle Zahlenkombinationen aus Lotto k=6 aus n=49 :13983816)

Kurz: Für grosse n musst du andere Wege gehen.

[Kegasetu]

Zitat:

Zitat von Michael II (Beitrag 1477133)

Zitat:

Zitat von Kegasetu (Beitrag 1477088)

Der Code funktioniert so weit. Nun bekomme ich aber das Problem, wenn ich mehr als 13 Stellen am Brett habe bekomme ich den Fehler: stack overflow

Es sollte schon möglich sein so um die 200 Stellen besetzten zu können.

Wie du später gemerkt hast, gibt's keinen Stack Overflow.

Wenn du aber echt mit 200 Stellen rechnen lassen willst, dann musst du dir bewusst sein, dass das Aufzählen aller möglichen Kombinationen länger dauern kann als wir alle warten können. Beispiel n=200 Stellen und an k=100 Stellen was reinhängen: 9.054851465610329e+58 mögliche Kombinationen.
(Alle Zahlenkombinationen aus Lotto k=6 aus n=49 :13983816)

Kurz: Für grosse n musst du andere Wege gehen.

Das Problem bin ich auch schon durchgegangen. Es gilt, k ist maximal 13 und zudem gibt es mehrere Möglichkeiten die passend sind, die Lösung liegt vermutlich im ersten zehntel der Zeit.

[Michael II]

Dann bist du bei maximal n=200 für maximal k=13 bei maximal 88326646952501950000 ;-). Viel Glück :thumb:

[Andreas13]

Sorry Kegasetu für meine böse Bemerkung: Aber ohne mathematische Kenntnisse kann man kein vernünftiges Computerprogramm "programmieren".
Die von Michael II genannte Aufzählung von 88326646952501950000 Varianten würde auf einem extrem starken PC (sagen wir großzügig 1 Milliarde Operationen pro Sekunde) über 2,8 TAUSEND Jahre dauern…
Denk mal darüber nach!
Gruß, Andreas

[Kegasetu]

Zitat:

Zitat von Andreas13 (Beitrag 1477139)

Sorry Kegasetu für meine böse Bemerkung: Aber ohne mathematische Kenntnisse kann man kein vernünftiges Computerprogramm "programmieren".
Die von Michael II genannte Aufzählung von 88326646952501950000 Varianten würde auf einem extrem starken PC (sagen wir großzügig 1 Milliarde Operationen pro Sekunde) über 2,8 TAUSEND Jahre dauern…
Denk mal darüber nach!
Gruß, Andreas

Abend, keine Sorge, Kritik ist erlaubt.
Natürlich habe ich mir Gedanken gemacht. Die meisten Kombinationen (>99,9999%) sind von vornherein ausgeschlossen. Es würde auch wenig Sinn ergeben diese zu bestimmen. Meine ursprüngliche Idee war es, irgendwie diese Kombinationen zu erstellen und vorher gezielt Plätze zu sperren. Um auf mein Beispiel zurückzukommen, Halterungen treten in einem Bereich von z.B. einem Meter auf und haben einen Mindestabstand, welcher zu Ende ist, sobald additiv eine Kraft überschritten wurde. Das Vorgehen wurde auch in einem Vorherigen Thema kurz angesprochen. Mein Problem ist wirklich "nur" die Informatik dahinter. Die Mechanik ist sehr simpel. Um herauszufinden was eine Halterung aushält, habe ich bereits Festigkeitsnachweise und FEM-Simulationen durchgeführt.
Ich habe mich bereits nach Unterstützung erkundigt (die natürlich entlohnt wird) um dieses Problem anzugehen. Also falls jemand Interesse hat kann er sich gerne melden.

Viele Grüße

[Kegasetu]

Hallo Zusammen.
Nur eine kleine Zwischenmeldung. Die grundlegenden Inhalte des Programmes sind fertig. Ich habe die Kombinationen zufällig ausgeben lassen, dies führt immer zu einem akzeptablen Ergebnis. Vielen Dank an Alle, die mich unterstützt haben!