Gruppenkombinationen mit verschiedenen Gruppenkapazitäten

Question

Nun, ich habe eine Frage, welcher Algorithmus für mein Problem am besten geeignet wäre. Nehmen wir an, ich habe 3 Gruppen:

Group A) 1 2 3 
Group B) 5 4 
Group C) 9 6 7 8 

Nun würde Ich mag alle möglichen Gruppen mit dieser Mitglieder bekommen (1-8) und Gruppen mit einer Kapazität 3, 2, 4.

Hinweis:

Group A) 3 1 2 
Group B) 5 4 
Group C) 7 8 9 6 

zählt als die gleiche Gruppenkombination wie obige Kombination.

Ich versuchte mit allen möglichen Kombinationen dieser Zahlen (1-8), aber wissend, dass ich eine Gruppe mit insgesamt 30 Mitgliedern hätte, hätte ich 265252859812191058636308480000000 verschiedene Kombinationen, aber das ist zu viel.

Ich versuchte nach nicht-isomorphen Gruppen zu suchen, hatte aber kein Glück.

Answer 1

Ich nehme an, dass keine Zahlen zweimal eingegeben werden können (Sie haben zwei 3er in Ihrem ersten Beispiel und zwei 5er in Ihrem zweiten ...), also werde ich nur die Nummern 1-9 und die gleiche Anzahl verwenden Elemente in jeder Gruppe.

Je nachdem, wie gut Sie Kombinatorik kennen, werden Sie mehr oder weniger davon verstehen - wenn Sie nicht verstehen, bitte fragen Sie und ich werde mein Bestes tun, um ausführlicher zu erklären.

Ihr Problem ist ein ziemlich Standard - Sie wollen einen Satz von 9 Elementen in Teilmengen von 3, 2 und 4 Elemente jeweils teilen. Dies wird als multinomial * bekannt und wird als so berechnet:

n = 9!/(3!*2!*4!) 

Im Grunde, was Sie tun, ist dies:

1) wählen 3 Elemente für die Gruppe A: n1 = 9 choose 3.
2) wählen 2 Elemente für Gruppe B: n2 = 6 choose 2.
3) die verbleibenden vier Elemente sind Gruppe C.

Total:

n = n1 * n2 = 9!/(3!6!) * 6!/(2!4!) = 9!/(3!*2!*4!) 

*) finden Sie im Abschnitt über "Partitionen"

EDIT: ich etwas über besondere Anforderungen bemerkt (6 Hasse 9, zum Beispiel) in einem Kommentar auf die Frage. Wenn Sie solche haben, schauen Sie zuerst zu ihnen (legen Sie die 9 in einer Gruppe, 6 in einer der anderen beiden) und dann zu den Resten zu sehen.