Gegeben eine Menge C mit n Elementen (Duplikate erlaubt) und eine Partition P von n
P = {i1, i2, ... / i1 + i2 + ... = n} Wie viele verschiedene Dekompositionen von C in Teilmengen der Größe i1, i2, ... gibt es?
Beispiel:
C = {2 2 2 3}
P = {2 2}
C = {2 2} U {2 3}
P = {1 1 2}
C = {2} U {2} U {2 3}
C = {2} U {3} U {2 2}
P = {1 3}
C = {2} U {2 2 3}
C = {3} U {2 2 2}
Ich habe eine Lösung, aber es ist ineffizient, wenn C mehr als ein Dutzend Elemente hat.
Danke im Voraus
Philippe
Antworten:
1 für die Antwort № 1Die Tatsache, dass dir die Reihenfolge der Zerlegung egal ist, macht es viel schwieriger. Das heißt, Sie sehen gerade {2 2} U {2 3} Das gleiche wie {2 3} U {2 2}. Trotzdem habe ich einen Algorithmus, der besser ist als der, den Sie haben, aber er ist nicht großartig.
Lassen Sie mich mit einem realistisch komplizierten Beispiel beginnen. Unser Satz wird sein A B C D E F F F F G G G G. Die Partition wird sein 1 1 1 1 2 2 5.
Meine erste Vereinfachung besteht darin, die Informationen, die uns im Set wichtig sind, mit der Datenstruktur darzustellen [[2, 4], [5, 1]], was bedeutet, dass 2 Elemente 4 mal wiederholt werden und 5 einmal wiederholt werden.
Meine zweite scheinbare Komplikation wird sein, die Partition mit darzustellen [[5, 1, 1], [2, 2, 1], [4, 1, 1]. Das Muster ist möglicherweise nicht offensichtlich. Jeder Eintrag hat die Form [size, count, frequency]. So wird die einzige Instanz von 2 Partitionen der Größe 2 zu [2, 2, 1]. Wir verwenden noch keine Frequenz, aber es zählt unterscheidbare Haufen gleicher Größe und Gemeinsamkeit.
Jetzt werden wir wie folgt rekrutieren. Wir nehmen das gebräuchlichste Element und finden alle Wege, es zu verwenden. In unserem Fall nehmen wir einen der Stapel der Größe 4 und finden, dass wir es wie folgt teilen können, indem wir jede verbleibende Partitionsstrategie neu anordnen lexikographische Reihenfolge:
[4]Verlassen[[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]].[3, [1, 0], 0]Verlassen[[2, 1, 1], [1, 1, 1], [2, 1, 1], [1, 4, 1]] = [[2, 1, 2], [1, 4, 1], [1, 1, 1]. (Beachten Sie, dass wir jetzt die Frequenz verwenden.)[3, 0, 1]Verlassen[[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]][2, [2, 0], 0]Verlassen[[3, 1, 1], [0, 1, 1], [2, 1, 1], [1, 4, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1]][2, [1, 1], 0]Verlassen[[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]][2, [1, 0], [1]]Verlassen[[3, 1, 1], [1, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1], [1, 1, 1]][2, 0, [1, 1]]verlassen '[[3, 1, 1], [2, 2, 1], [0, 2, 1], [1, 2, 1]] = [[3, 1, 1], [2, 2, 1], [1, 2, 1]] 1[1, [2, 1]]Verlassen[[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]][1, [2, 0], [1]]Verlassen[[4, 1, 1], [0, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[4, 1, 1], [2, 1, 1], [1, 3, 1]][1, [1, 0], [1, 1]]Verlassen[[4, 1, 1], [1, 1, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[4, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 1]][1, 0, [1, 1, 1]]Verlassen[[4, 1, 1], [2, 2, 1], [0, 3, 1], [1, 1, 1]] = [[4, 1, 1], [2, 2, 1], [1, 1, 1]][0, [2, 2]]Verlassen[[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]][0, [2, 1], [1]]Verlassen[[5, 1, 1], [0, 1, 1], [1, 1, 1], [0, 1, 1], [1, 3, 1]] = [[5, 1, 1], [1, 3, 1], [1, 1, 1]][0, [2, 0], [1, 1]]Verlassen[[5, 1, 1], [0, 2, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1], [2, 1, 1], [1, 2, 1]][0, [1, 1], [1, 1]]Verlassen[[5, 1, 1], [1, 2, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1,], [1, 2, 2]][0, [1, 0], [1, 1, 1]]Verlassen[[5, 1, 1], [1, 1, 1], [2, 1, 1], [0, 3, 1], [1, 1, 1]] = [[5, 1, 1], [2, 1, 1], [1, 1, 2]][0, 0, [1, 1, 1, 1]]Verlassen[[5, 1, 1], [2, 2, 1], [0, 4, 1]] = [[5, 1, 1], [2, 2, 1]]
Nun kann jedes dieser Teilprobleme rekursiv gelöst werden. Das mag sich anfühlen, als wären wir auf dem Weg, sie alle zu konstruieren, aber wir sind es nicht, weil wir memoize die rekursiven Schritte. Es stellt sich heraus, dass es viele Möglichkeiten gibt, wie die ersten beiden Gruppen von 8 mit den gleichen 5 übrig bleiben. Mit Memoization müssen diese Lösungen nicht wiederholt neu berechnet werden.
Das heißt, wir werden es besser machen. Gruppen von 12 Elementen sollten kein Problem darstellen. Aber wir tun es nicht Das viel besser. Ich würde mich nicht wundern, wenn es irgendwo um Gruppen von etwa 30 Elementen mit interessanten Partitionen herum zerfällt. (Ich habe es nicht codiert. Es kann mit 30 gut sein und mit 50 kaputt gehen. Ich weiß es nicht wo es zusammenbrechen wird. Aber da man über Partitionen hinweg iteriert, ist es an einem ziemlich kleinen Punkt werden Nervenzusammenbruch.)
0 für die Antwort № 2
Alle Partitionen können in 2 Stufen gefunden werden.
Erstens: von P mache eine neue geordnete Partition von n, P_S={P_i1, P_i2, ..., P_ip}, summiert identische i "s.
P = {1, 1, 1, 1, 2, 2, 5}
P_S = (4, 4, 5)
Stellen Sie Partitionen her {C_i1, C_i2, ..., C_ip} von C in Gedenken an P_S. Hinweis, C_ix ist multi-set wie C. Es teilt C in Multi-Sets nach den Größen der letzten Partitionen auf.
Zweitens: für jeden {C_i1, C_i2, ..., C_ip} und für jeden ix, x={1,2,...,p} Finde die Anzahl der Partitionen von C_ix in t (Anzahl von ix"s im P) setzt mit ix Elemente. Ruf diese Nummer an N(C_ix,ix,t).
Die Gesamtzahl der Partitionen ist:
sum by all {C_i1, C_i2, ..., C_ip} ( product N(C_ix,ix,t) ix={1,2,...,p} )
Der erste Teil kann rekursiv ganz einfach gemacht werden. Der zweite ist komplizierter. Partition von Multi-Set M in n Teile mit k elements ist das selbe wie das Auffinden aller partiell sortierten Listen mit Elementen aus M. Teilweise Bestellliste ist vom Typ:
a_1_1, a_1_2, ..., a_1_k, a_2_1, a_2_2, ..., a_2_k, ....
Woher a_i_x <= a_i_y ob x < y und (a_x_1, a_x_2, ..., a_x_k) lexicographic <= (a_y_1, a_y_2, ..., a_y_k) ob x < y. Mit diesen 2 Bedingungen ist es möglich, alle Partitionen von zu erstellen N(C_ix,ix,t) rekursiv.
Für einige Fälle N(C_ix,ix,t) ist einfach zu berechnen. Definieren |C_ix| als Anzahl der verschiedenen Elemente in Multi-Set C_ix.
if t = 1 than 1
if |C_ix| = 1 than 1
if |C_ix| = 2 than (let m=minimal number of occurrences of elements in C_ix) floor(m/2) + 1
in general if |C_ix| = 2 than partition of m in numbers <= t.