Group combinations with different group capabilities
Well, I have a question about which algorithm would be the most suitable for my problem. Let's say that I have 3 groups:
Group A) 1 2 3
Group B) 5 4
Group C) 9 6 7 8
Now I would like to get all possible groups with these members (1-8) and groups with capacity 3, 2, 4.
Note:
Group A) 3 1 2
Group B) 5 4
Group C) 7 8 9 6
is considered the same group combination as above.
I have tried with all possible combinations of these numbers (1-8), but knowing that I can have groups with 30 members, I would choose 265252859812191058636308480000000 different combinations, but this is too many.
I have tried searching for non-isomorphic groups but no luck.
I am assuming no numbers can be entered twice (you have two 3s in the first example and two 5s per second ...), so I will use numbers 1-9 and the same number of items in each group.
Depending on how well you know combinatorics, you will more or less understand this - if you don't understand, ask and I will do my best to explain in more detail.
Your problem is pretty standard: you want to split a set of 9 elements into subsets of 3, 2 and 4 elements, respectively. This is called multinomial * and is calculated like this:
n = 9! / (3!*2!*4!)
Basically what you do:
1) select 3 items for group A: n1 = 9 choose 3.
2) select 2 items for group B: n2 = 6 choose 2.
3) the other four items are group C.
Total:
n = n1 * n2 = 9!/(3!6!) * 6!/(2!4!) = 9! / (3!*2!*4!)
*) See the section "Sections"
EDIT: I noticed something about special requirements (like 6 hates 9) in the comment to the question. If you have, look at them first (put 9 in one group, 6 in one of the other two) and then look at the leftovers.
a source to share