ich hätte mal ne Frage, die mich schon seit Tagen quält, aber ich keinen Ansatz finde.
Ich suche einen Algorithmus zu einem eigentlich „trivialen“ Problem, ohne eine Lösung zu finden.
Das Beispiel im Folgende ist nur für m=5 und n=3 gedacht, wobei m und n im Eigentlichen viel höher sind.
Ich will (statistisch gesehen) 5 Kugeln auf 3 Töpfe verteilen, wobei die Anzahl der Kugeln in den Töpfen unterschiedlich hoch, aber nicht 0 sein dürfen!
Bspw.
Topf 1: 1,2,3
Topf 2: 4
Topf 3: 5
oder
Topf 1: 1,2
Topf 2: 3,4
Topf 3: 5
Nicht möglich sein darf aber bspw.
Topf 1: 3,4
Topf 2: 1,2
Topf 3: 5
Da dies gleich dem oberen Bsp. wäre.
Ich suche als Output alle zulässigen Kombinationen, wobei eben m und n variabel gehalten werden müssen!
Hat irgendjemand etwas in petto oder eine Ahnung, ob es solch ein Problem aus einem anderen Bereich gibt?
da jeder Topf eine Kugel enthalten soll bleiben m-n Kugeln, die beliebig auf n Töpfe verteilt werden sollen.
Stellt man sich jetzt die Töpfe und Kugeln mal bildlich nebeneinander gestellt vor, so ergibt sich (ohne die schon in den Töpfen enthaltene erste Kugel) exemplarisch folgendes Bild:
00|000|0||0
Der erste Topf enthält in diesem Beispiel zwei weitere Kugeln, der Zweite drei, der Dritte eine, der Vierte keine und der Fünfte eine weitere Kugel. Ich denke es ist klar, dass sich auf diese Weise alle Möglichkeiten darstellen lassen. Gleichzeitig ist auch jede Darstellung eine Möglichkeit.
Das Problem reduziert sich somit auf die Anzahl der Permutationen von n-1 Strichen und m-n Nullen:
\frac{((n-1)+(m-n))!}{(n-1)!*(m-n)!}
Das ist allerdings nicht alleine auf meinem Mist gewachsen, sondern ich habe mich folgender Hilfe bedient: http://www.ingo-bartling.de/mathe/klasse12/html/stoc…
Dort ist das ganze auch noch etwas umfangreicher erklärt.
leider bringt das Nix, weil damit auch „0er“ in den Töpfen zugelassen sind. Es geht eher um das aus der Stochastik bekannte Problem „Verteilung von unterscheidbaren Schülern auf unterscheidbare Gruppen“ (siehe auch hier: http://www.matheboard.de/archive/390537/thread.html). Allerdings schaffe ich es trotzdem nicht für alle m und n eine sinnvolle Aufteilung zu bekommen…
jedem Topf wurde doch zu Beginn schon eine Kugel zugeteilt… Da wo also „keine“ Kugel drinnen ist befindet sich neben der Enthaltenen bloß keine Weitere…
Sonst hätte man sich auch den Aufwand mit den m-n Kugeln sparen können.