Grouping problem

Question

Well, I have a question about what algorithm would be most appropriate 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 this 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

counts as same group combination as above combination.

I tried with all possible combinations of this numbers (1-8) but knowing that I might have a groups with total of 30 members I would came up with 265252859812191058636308480000000 different combinations, but that is to many.

I tried to search for non-isomorphics grups, but had no luck.

Answer 1

I assume that no numbers can be entered twice (you have two 3's in your first example, and two 5's in your second...), so I'll just be using numbers 1-9 and the same number of elements in each group.

Depending on how well you know combinatorics, you will understand more or less of this - if you don't understand, please ask and I'll do my best to explain in more detail.

Your problem is a pretty standard one - you want to divide a set of 9 elements into subsets of 3, 2 and 4 elements respectively. This is known as a multinomial*, and is calculated as so:

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

Basically, what you do is this:

1) choose 3 elements for group A: n1 = 9 choose 3.
2) choose 2 elements for group B: n2 = 6 choose 2.
3) the remaining four elements are group C.

Total:

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

*) See the section about "Partitions"

EDIT: I noticed something about special requirements (6 hates 9, for instance) in a comment to the question. If you have such, see to them first (place the 9 in one group, 6 in one of the other two) and then see to the leftovers.