Mathematisches Problem...

Hallo Leute,

ich möchte den Rechenaufwand für einen bestimmten Algorithmus abschätzen, und hoffe daß ihr mir dabei helfen könnt.


Zunächst mal ein vereinfachtes Beispiel:
Wenn ich wissen möchte wie viele Möglichkeiten es gibt um n Objekte in einer Reihe anzuordnen, so errechne ich das ja mit n!, richtig?

also bei 5 Objekten gäbe es dann 5! = 120 Möglichkeiten


Wenn man eine Liste mit n Objekten hätte geht es also im wesentlichen darum, daß nach dem platzieren eines Objektes noch n-1 Objekte übrig sind. Die Länge der Liste verringert sich also nach jedem Schritt um 1.


soweit so gut...
mein Problem ist leider etwas komplizierter

ich habe n Muster, die in einer Reihe angeordnet werden sollen, wobei es für jedes Muster aber nicht n-1 sondern m mögliche Nachfolger gibt. Außerdem verringert sich die Länge der Liste nicht um 1, sondern um k.

n ist festgelegt, m und k sind aber von Muster zu Muster unterschiedlich, so daß nur Durchschnittswerte bekannt sind.


Wie kann ich die Anzahl der möglichen Kombinationen anhand dieser Werte abschätzen?


Falls euch das zu theoretisch ist, dürft ihr natürlich auch gerne irgendein Zahlenbeispiel nutzen, z.B. 100 Muster mit jeweils durchschnittlich 125 möglichen Nachfolgern (ja, m kann größer sein als n, muss aber nicht), wobei in jedem Schritt vielleicht ca. 3 Muster wegfallen.


Irgendwelche Ideen?


PS:
nein, es ist definitiv nicht möglich einfach alle Kombinationen zu berechnen und diese dann zu zählen, denn selbst 100 Muster (im "einfachen" Fall also 9*10^157 Kombinationen!!) sind noch ein sehr harmloses Beispiel, es können genausogut auch 1000 oder sogar 10000 Muster sein.

Hi,

Zitat:

---

Wenn ich wissen möchte wie viele Möglichkeiten es gibt um n Objekte in einer Reihe anzuordnen, so errechne ich das ja mit n!, richtig?

---

Jo

So jetzt zu deinem Problem:
Ich würde sagen n*m^(n/k-1)

MfG Jeffrey

edit: ich hoff ich hab die Aufgabe richtig verstanden. Für was brauchst du das denn? Vielleicht versteht man es dann besser

Zitat:

---

ich hoff ich hab die Aufgabe richtig verstanden. Für was brauchst du das denn? Vielleicht versteht man es dann besser

---

Naja, um Muster in einer bestimmten Art anzuordnen...


Ich versuche mal es etwas anschaulicher zu erklären...

Nehmen wir mal folgende Situation:
Es gibt 5 (Spiel-)Würfel in verschiedenen Farben, die in eine Reihe gelegt werden sollen.

Berücksichtigt man dabei nur die Farbe, so gibt es dafür 5! = 120 verschiedene Möglichkeiten.


Und jetzt stelle man sich 5 Listen vor, eine für jeden Würfel...
und auf jeder Liste steht jeweils welche Würfel man rechts neben den Würfel legen darf zu dem die Liste gehört.


Und als wenn das noch nicht kompliziert genug wäre, stehen nicht nur die Farben der "erlaubten" Nachbarn auf diesen Listen, sondern jeweils auch noch welche Zahl oben liegen muss.


so könnte auf einer Liste für einen grünen Würfel z.B. stehen
rot 1
rot 3
rot 4
blau 6
gelb 5
gelb 6


Und jetzt ist die Frage eben, wieviele mögliche Kombinationen es gibt, wenn man diese Randbedingungen berücksichtigt.

Bekannt sind, wenn wir mal beim Würfelbeispiel bleiben, die Anzahl der Würfel (n), die durchschnittliche Gesamtlänge einer Liste (m), und wie oft eine Farbe durchschnittlich auf so einer Liste vorkommt (k).


Natürlich sind die Listen selbst auch alle bekannt, aber ich wüsste nicht was man außer m und k davon noch benötigen könnte, um die Anzahl der möglichen Kombinationen zu berechnen.


Sowohl m als auch k bewegen sich übrigens bei allen Listen etwa in der gleichen Größenordnung, die Verwendung der Mittelwerte sollte also eine ganz ordentliche Schätzung ermöglichen.



Ich hoffe mal, daß diese Beschreibung mein Problem etwas verständlicher darstellt.

Zitat:

---

n*m^(n/k-1)

---

Wäre diese Formel unter Berücksichtigung meiner verbesserten Problembeschreibung noch korrekt?

Mal ne dumme Frage ist das jetzt ein Urnenproblem mit Zurücklegen oder ohne? Oben sprichst du von 5 verschieden Farbige Würfel, die nacheinander hingelegt werden. Bei deiner Liste, legst du dann manche dreimal hin. Hast du jetzt die Würfel beliebig oft zur Hand (mit zurücklegen) oder nicht?

und das durschnittliche Vorkommen einer Farbe ist ein bisschen komisch. Dann gehst du ja von einem Erwartungswert aus.

Ich überleg mirs mal genauer aber vielleicht wählst du noch ein anderes beispiel bzw. präzisierst dein genanntes.

Danke ich freu mich schon auf die Aufgabe!

Martin

Es gibt in meinem Beispiel nur die 5 genannten Würfel, diese dürfen allerdings nicht beliebig aneinandergereiht werden...
(die Listen geben nicht an was hingelegt wurde, sondern was neben einen bestimmten Würfel gelegt werden darf, und wie)

Wenn man also den grünen Würfel aus dem Beispiel betrachtet, so darf man daneben entweder den roten, den blauen oder den gelben legen...


aber nicht irgendwie, sondern nur in einer bestimmten Ausrichtung...
wählt man den roten aus, so muss entweder die 1, die 3 oder die 4 oben liegen, alles andere ist nicht erlaubt.

Mit dem durchschnittlichen Vorkommen einer Farbe meine ich einfach nur, daß wenn man die Listen betrachtet, jeder Würfel (also jede Farbe) durchschnittlich k mal vorkommt.

bei der Beispielliste gibt es rot dreimal, blau einmal und gelb zweimal... Mittelwert davon ist 2, also wäre k für diese Liste 2. Allerdings ist das oben erwähnte k wiederum der Mittelwert für alle Listen... das stellt aber kein Problem dar, da k bei allen Listen ungefähr gleich groß ist

Hi,
ich blick jetzt leider net, wirklich, was k ist. Du hast doch gemeint, dass k die Zahl ist, um die sich die Listenlänge reduziert.
Bei deinem Würfelbeispiel stimmt das mit den Nachfolgern ja nicht ganz. bei deinem Beispiel hast du weiterhin nach dem ersten zug noch 4 weitere würfel. Also bleibt die anzahl an möglichkeiten weiter 120. du kannst dann halt die würfel nur in einer bestimmten art anordenen.
mfg jeffrey

Zitat:

---

Zitat von jeffrey

ich blick jetzt leider net, wirklich, was k ist. Du hast doch gemeint, dass k die Zahl ist, um die sich die Listenlänge reduziert.

---

Ok, da habe ich mich etwas unklar ausgedrückt...
ich denke mein neues Beispiel ist etwas eindeutiger

Zitat:

---

Bei deinem Würfelbeispiel stimmt das mit den Nachfolgern ja nicht ganz. bei deinem Beispiel hast du weiterhin nach dem ersten zug noch 4 weitere würfel. Also bleibt die anzahl an möglichkeiten weiter 120. du kannst dann halt die würfel nur in einer bestimmten art anordenen.

---

Stimmt, es bleiben 4 Würfel übrig, aber es müssen trotzdem mehr Möglichkeiten sein als 120.
Warum das so ist, versuche ich mit einem neuen Beispiel zu erklären.

====================

Also ich gehe das mal konkret für ein paar Würfel durch, in der Hoffnung daß ich es schaffe es verständlich zu erklären...


Vorbedingungen:
- Es sind 5 (Spiel-)Würfel in 5 verschiedenen Farben vorhanden, z.B. rot, grün, blau, gelb und weiß
- Es gibt für jeden Würfel eine Liste, also eine rote, eine grüne, eine blaue etc.

Die Würfel sollen jetzt in eine Reihe gelegt werden, wobei der Ablauf wie folgt aussehen könnte:

1. Ich nehme einen der Würfel, z.B. den blauen, und lege ihn irgendwie hin. (welche Zahl nach oben zeigt spielt keine Rolle)

2. Ich schaue auf die blaue Liste, denn dort steht welche Würfel ich rechts neben den blauen legen darf, z.B. rot, grün und weiß.

3. Ich nehme einen der "erlaubten" Würfel, vielleicht den weißen, und schaue ein weiteres mal auf die blaue Liste, um festzustellen welche Zahlen beim weißen Würfel oben liegen dürfen wenn man ihn rechts neben den blauen Würfel legt. Also angenommen auf der blauen Liste steht zweimal "weiß", und zwar einmal mit einer 3 und einmal mit einer 5, dann darf ich den weißen Würfel entweder mit der 3 oder mit der 5 nach oben neben den blauen Würfel legen.

4. Es liegen jetzt 2 Würfel auf dem Tisch, der blaue in irgendeiner beliebigen Orientierung, und der weiße rechts daneben, z.B. mit der Zahl 3 nach oben (aber nicht etwa mit der 4 oder der 1, denn diese standen nicht zur Verfügung)

5. Ich nehme die weiße Liste zur Hand, und sehe nach welche Würfel ich rechts neben den weißen Würfel legen darf, vielleicht blau und gelb. Da der blaue bereits auf dem Tisch liegt muss ich den gelben wählen.

6. Ich sehe nochmal auf der weißen Liste nach, welche Zahlen beim gelben Würfel oben liegen dürfen, wenn er rechts neben dem weißen Würfel liegt, vielleicht die 1, 2, 5 und 6, und lege den Würfel mit einer dieser Zahlen nach oben rechts neben den weißen Würfel.

etc. etc. etc.


also nochmal zusammengefasst:
Zu jedem Würfel existiert eine Liste, und auf dieser Liste steht drauf, welche anderen Würfel rechts neben den zur Liste gehörenden Würfel gelegt werden dürfen, und welche der 6 theoretisch möglichen Orientierungen jeweils erlaubt sind.


Und gesucht ist wie gesagt die Anzahl aller möglichen Kombinationen, die aber mit Sicherheit deutlich über 120 liegen wird, da ja bei jedem Schritt unter Umständen mehr Varianten zur Auswahl stehen können, als noch Würfel übrig sind.

Nehmen wir dazu nur mal den grünen Würfel vom letzten Beispiel...
dessen Liste hatte 6 Einträge, obwohl es neben dem grünen nur 4 weitere Würfel gibt.



Bei den Listen ist es dabei wie gesagt so, daß alle ungefähr gleich lang sind, und auch eine ähnliche Anzahl an Farben (also anderen Würfeln) enthalten. Die Listen enthalten vielleicht durchschnittlich 6 Einträge (das ist m), und es stehen durchschnittlich 3 verschiedene Würfel drin. Die in einer Liste vorhandenen Würfel wären also im Schnitt mit jeweils 2 Einträgen vertreten (das ist k).


edit:
falls m und k zur Berechnung der möglichen Kombinationen ungeeignet sind, können natürlich auch irgendwelche anderen Größen verwendet werden, die sich aus den Listen gewinnen lassen.
(die Listen selbst sind ja alle vorhanden)




Oder wenn ihr mögt stellt euch keine Würfel vor, sondern vielleicht Pokerchips oder sowas...
in diesem Fall gäbe es dann jeweils 6 Chips von einer Farbe, die eben mit unterschiedlichen Nummern beschriftet sind.
(wobei dann aber jede Farbe nur einmal verwendet werden dürfte)

hi,
ich glaube, jetzt blick ich es mehr, ein würfel hat jetzt also nicht mehr nur noch eine eigenschaft, sondern 6 + farbe.
jetzt ist nur noch die frage, wieviele würel es insgesammt gibt. n? und jedes mal wird es einer weniger? also sind insgesamt n durchgänge zu machen?
wieviele möglichkeiten gibt es beim ersten mal hinlegen? beim würfelbeispiel n*6, nennen wir es mal r.
aus der liste fliegen also immer die möglichkeiten raus, welche farben schon gezogen sind.
dann müsste als formel folgendes gelten:
r*m*(m-k)*(m-2k)*(m-3k)*...*(m-(n-3)k)*(m-(n-2)k)
wie das jetzt als formel mit hochzahlen und fakultät aussieht weiß ich nicht, ka, ob das überhaupt geht, aber rekursiv sollte sich das ganz berechnen lassen.
so, hoffe dir damit geholfen zu haben, und dass das stimmt.
mfg jeffrey

Zitat:

---

Zitat von jeffrey

ich glaube, jetzt blick ich es mehr, ein würfel hat jetzt also nicht mehr nur noch eine eigenschaft, sondern 6 + farbe.
jetzt ist nur noch die frage, wieviele würel es insgesammt gibt. n? und jedes mal wird es einer weniger? also sind insgesamt n durchgänge zu machen?

---

genau

Zitat:

---

wieviele möglichkeiten gibt es beim ersten mal hinlegen? beim würfelbeispiel n*6, nennen wir es mal r.

---

ok, soweit klar...
bei 5 Würfeln wäre das also 30
(bei meiner Eigentlichen Anwendung läge dieser Wert irgendwo zwischen 144 und 14400)

Zitat:

---

aus der liste fliegen also immer die möglichkeiten raus, welche farben schon gezogen sind.

---

seh ich auch so, allerdings fällt mir dabei gerade auf, daß k vielleicht doch etwas ungeschickt gewählt ist...

Es steht ja nicht jeder Würfel in jeder Liste, wenn man einen Würfel ablegt fällt bei manchen Listen also garnichts weg, und bei anderen vielleicht 2 oder 3 Einträge. Ich vermute da wäre es wohl besser k so zu definieren, daß es die Häufigkeit jedes Würfels in jeder Liste angibt... ok, schlecht erklärt... also bei der Liste vom grünen Würfel war rot 3x, blau 1x und gelb 2x drin. Addiert wären das 6, und es stehen 3 Würfel in der Liste, also wäre k dann 2, aber es ist wohl sinnvoller auch die nicht vorhandenen Würfel zu berücksichtigen also statt 6/3 eben 6/4 = 1,5 zu nehmen, weil der 4. verbleibende Würfel eben 0x in der Liste steht...

Zitat:

---

r*m*(m-k)*(m-2k)*(m-3k)*...*(m-(n-3)k)*(m-(n-2)k)

---

danke für die Formel,
ich gehe das mal Schritt für Schritt durch...

- Am Anfang gibt es r Möglichkeiten
- Beim zweiten Schritt gibt es dann für jeden "Anfangswürfel" nochmal m Mögliche Nachfolger
- Beim dritten Schritt fallen durchschnittlich etwa k Einträge aus allen Listen weg, es bleiben also dann nurnoch m-k mögliche Nachfolger

und das geht dann so weiter, aber nur bis (n-2)*k, weil k ja bei den ersten beiden Schritten noch nicht beachtet wurde.


habe ich das so richtig verstanden?

hi

Zitat:

---

und das geht dann so weiter, aber nur bis (n-2)*k, weil k ja bei den ersten beiden Schritten noch nicht beachtet wurde.

---

genau, es gibt ja n ziehungen, deswegen nur bis n-2. m ist ja (n-1)*k, zumindest bei dem neuen k. ich denke, dass sollte so einigermaßen hin kommen.
mfg jeffrey

Naja aber dann hast du nur die durschnittlichen Möglichkeiten nicht die exakte Anzahl. Dafür bräuchste du noch die Information wie oft jede Farbe auf der Liste steht.

Bei deiner Formel

ich würds so machen

n * 6 * (n - 1)! * 2^(n-1) = n! * 6 * 2^(n-1)

immerhin hast du bei n Farben n Möglickeiten für die Farbwahl, bei der zweiten Eigenschaft der Augenzahl hast du bei einem normalen Würfel 6 Möglichkeiten (ich glaub jeffrey des fehlt bei deiner Formel). die folgenden Würfel haben dann nur noch (n-1)! Farben zur Auswahl und durchschnittlich zwei Augenzahlen.

Vorteil dieser Formel. Die Listenlänge ist nicht nötig, da man von der reduzierung der möglichen Farben ausgeht und sich zwangsläufig dadurch die Liste um durchschnittlich zwei reduziert. Vorteil von Jeffreys Formel: Die Anzahl der verschiedenen Augenzahlen ist unwichtig, oder wurde zumindestens jetzt noch nicht beachtet.


KANN GUT SEIN DAS MEINE LÖSUNG VÖLLIG FALSCH IST. Dann bitte ich um nachsicht. Aber sagt mir dann bitte was ich falsch gemacht habe. Vielen Dank. Ich hoffe ich konnte weiterhelfen.

hi,

Zitat:

---

n * 6 * (n - 1)! * 2^(n-1) = n! * 6 * n!/n * 2 = (n!)^2 * 12 / n

---

also die formel denke ich, ist total falsch, habe auch nicht wirklich verstanden, wie du da drauf gekommen bist. außerdem stimmt deine umformung nicht:
n*6*(n-1)!*2^(n-1)=6*n!*2^(n-1)
du berücksichtigst nicht, dass nicht alle zahlen in der nachfolgerliste vorkommen. aber selbst wenn man das vernachlässigst denke ich, stimmt die formel nicht, dann wäre es n!*6^n

die augenzahlen kommen bei mir natürlich auch vor, und zwar in m.

mfg jeffrey

Ok die umformung ist falsch ich hab sie hingeschrieben und dann nochmal die Formel ausgebessert. Muss natürlich 6n!*2^(n-1) sein.

Naja wie drauf gekommen bin.
Erster Würfel: n Farben und 6 Möglichkeiten für Augenzahlen -> n* 6
Zweiter Würfel: hat nur noch n-1 Farbmöglichkeite und nachdem auf der Liste die Farbe durschnittlich 2 mal vorkommt, gibt es auch 2 verschiedene Augenzahlen zur Auswahl (n-1) * 2 * (n-2)*2 ...
das pflanzt sich soweit fort, bis beim letzten Würfel nur noch eine Möglichkeit für die Farbe übrig ist. Für die Augenzahl gibt es trotzdem zwei verschiedene Möglichkeiten.

also n* 6 * (n-1)! * 2^(n-1).

So jetzt zu deinem Argument. Es ist gegeben, dass auf jeder Liste durchschnittlich zweimal die Farbe vorkommt. Mit unterschiedlichen Zahlen. Beim ersten Würfel hab ich 6 Zahlen zur auswahl bei den restlichen nur noch 2. Du machst ja auch nix anderes. Du ziehst ja auch immer k ab.Nur ist dein Ansatz, dass du von einer vollen Liste ausgehst und jedesmal den durchschnittswert abziehst und ich geh davon aus, dass die Liste durch die angabe des durchschnittswertes überflüssig wird. Ist natürlich nur eine Näherun genauso wie deine.

Naja so leicht gebe ich meine Formel nicht auf. immerhin kann man sich dadurch eine Information sparen! Ich hoffe ich hab jetzt den Ansatz ausführlich und verständlich genug erklärt. (der Fehler oben in der Formel ist nachträglich ausgebessert)


Mir ist grad noch aufgefallen, dass ja nicht jeder Würfel auf der Liste vorkommt. Ich bin vom Gegenteil asugegangen. Ich rechne jetzt mal nach was des für einen Unterschied macht, ist ja alles nur genähert und poste dann wieder.

Hi,
jetzt blick ich das auch, was du meinst. wußte nicht, wo die 2 hekommt. übrigens sind wir inzwischen bei k=1,5 ;-) aber das ist ja egal, ist ja nur ein beispiel. das man sich eine angabe sparen kann ist auf jeden fall richtig. weil m=k*(n-1) ist. könnte man bei mir auch einsetzten.
r ist die anzahl der möglichkeiten beim ersten hinlegen, es kann ja theoretisch hier auch scho einschränkungen geben.
deine formel ist dann also
r*(n-1)!*k^(n-1)
wenn du m=k*(n-1) in meine formel einsetztst komt genau das gleiche raus :-)
wir sind uns also einig :-D
mfg jeffrey

stimmt. Aber irgendwie gefällt mir des durchschnittliche nicht. des ist so ungenau. Wäre schön wenn man wüsste, wie oft jede Farbe vorkommt.

Aber man kann halt nicht alles im leben haben ;)

Zitat:

---

stimmt. Aber irgendwie gefällt mir des durchschnittliche nicht.

---

mir auch nicht...
aber wenn ich mich nicht sehr irre, dürfte es absolut unmöglich sein, die Anzahl exakt auszurechnen.

Das Problem ist ja daß die Listen alle unterschiedlich sind.
angenommen ich darf z.B. neben den gelben Würfel den weißen legen, dann heißt das aber noch lange nicht, daß ich auch neben den weißen Würfel den gelben legen darf.


Um die exakte Anzahl zu bestimmen müsste ich also tatsächlich alle Kombinationen ausrechnen, und das dauert bei meiner konkreten Anwendung selbst bei sehr optimistischen Schätzungen schon erheblich länger als das Universum alt ist.


Ok, vielleicht liege ich damit auch falsch, und es gibt eine einfachere Lösung um die Anzahl aller Kombinationen zu bestimmen. Also wenn in der Richtung noch Jemandem was einfällt, immer her damit

An Informationen sind wie gesagt sämtliche Listen vollständig vorhanden, um beim Würfelbeispiel zu bleiben könnte also z.B. auch berechnet werden wie oft der rote Würfel mit einer 4 in den Listen vorkommt oder sowas.



Ich bin jetzt übrigens auf noch ein anderes Problem gestoßen...
ich habe jeffreys Formel mal in Matlab umgesetzt, und erhalte als Ergebnis leider nur "Inf", da Matlab keine Zahlen darstellen kann die größer sind als ungefähr 10^308 :shock:


edit:

Zitat:

---

r*(n-1)!*k^(n-1)

---

hmm...
also wenn ich das jetzt noch richtig im Kopf habe, wäre n in meinem Fall 432, und r ebenfalls (da bei meiner Anwendung unterschiedliche Orientierungen des ersten "Würfels" nicht berücksichtigt werden müssen)
und k müsste eigentlich 0,5 sein oder sowas in der Größenordnung.
(die Listen haben alle etwa 215 Einträge, und die "Farben" sind gleichmäßig verteilt)

Wenn ich das jetzt mal in den Windows-Rechner eingebe...
r = 432
(n-1)! = 431! = 9,9*10^949
=> r * (n-1)! = 4,3*10^952

k^(n-1) = 0.5^431 = 1,8*10^-130

=> r * (n-1)! * k^(n-1) = 7,7*10^822

kommt das in etwa hin?

Hi,
das ist aber groß. Was sind denn n, k, m bei dir? Probier mal die andere Formel, ob da auch inf raus kommt, das ist ja die gleiche Formel, nur anders dargestellt.
MfG Jeffrey

jo, hab ich gerade mal ausprobiert, steht in meinem letzten post


aber nochmal etwas übersichtlicher:

n = 432
r = 432
m = 215
k = 0.5

Hi,
das ist ja ganz schön viel, laut Formel stimmt das. Allerdings kan ich in keinster Weise abschätzen, ob das realistisch ist.
Aber ich denke die Formel könnte stimmen, nachdem wir hier unabhängig auf verschiedenen Wegen zum gleichen Ergebnis gekommen sind. Auch wenn ich es nicht gleich erkannt habe ;-)
MfG Jeffrey

Zitat:

---

das ist ja ganz schön viel

---

und dabei ist das noch der "harmlose" Fall mit n=432 ...
für n=4800 soll das auch nochmal ausgerechnet werden, das kann ich allerdings erst in 1-2 Tagen machen, wenn mein Computer endlich alle 4800 Listen berechnet hat.

Zitat:

---

Allerdings kan ich in keinster Weise abschätzen, ob das realistisch ist.

---

Naja, ich hoffe einfach mal daß es stimmt...
zumal 432! ja irgendwas um 10^950 rum ist, also kann das Ergebnis so falsch wohl nicht sein

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

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.

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.

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.