Mathematisches Problem...

[jeffrey]

hi,
für was brauchst du das denn überhaupt?
mfg jeffrey

[Felix G]

Ich habe einige zweidimensionale Muster, und die sollen aneinandergereiht werden...

Dabei passen manche Muster aber nicht zusammen, und einige nur wenn man sie gegeneinander verschiebt.


Als erstes berechne ich also Listen, eine für jedes Muster, in denen jeweils drin steht welche anderen Muster da dran passen, und natürlich ob bzw. wie diese ggf. verschoben werden müssen. Das dauert leider recht lange, zumindest für die 4800 Muster mit denen mein Computer gerade zu kämpfen hat (die 432 Listen waren dagegen in ca. 5 Minuten berechnet).

Im zweiten schritt werden die Muster dann zusammengesetzt, wobei ich aber natürlich bei der ersten gefundenen Kombination abbreche.


Dennoch möchte ich natürlich gerne wissen wie lange es wohl dauern könnte, alle möglichen Kombinationen zu erzeugen.

[phaidros]

Suche mal nach Polya Counting Theory.
Das lässt sich, wenn ich alles richtig verstanden habe, sehr wohl genau ausrechnen.
Vergiss doch mal das Würfel-Beispiel. Das verwirrt nur, Erkläre mal genauer, wenn du möchtest, das eigentliche Problem.
Klingt bis jetzt schon mal sehr interessant.

[Felix G]

Naja, ich dachte eigentlich daß das Würfelbeispiel schon ganz gut passt...

Und beim eigentlichen Problem geht es wie gesagt darum, eine Menge von n Mustern so in eine Reihe zu legen, daß sie "aneinander passen".

Ich habe also für jedes Muster eine Liste, in der steht welche anderen Muster rechts neben das betrachtete Muster passen, und ob diese evtl. verschoben werden müssen.

in der Liste für Muster 25 könnte also vielleicht stehen, daß Muster 62 rechts daneben platziert werden darf, und zwar entweder normal oder um 1 nach oben verschoben.

Wenn die Muster aneinandergereiht werden, wird das erste Muster immer direkt, also unverschoben verwendet, und die anderen werden halt so dran gehängt daß sie passen.

Diese Listen zu berechnen dauert eine ganze Weile, weil einiges überprüft werden muss um festzustellen ob ein Muster passt, dafür erleichtern und beschleunigen sie aber das Zusammensetzen.


Von dieser Polya Counting Theory habe ich noch nie was gehört. Ich werde mir das aber mal genauer anschauen, obwohl ich mir nicht vorstellen kann daß eine exakte Berechnung bei einem derartigen Problem möglich ist.