I've tried searching around, but I think I'm not familiar with the terminology to find the correct terms to search for.
Anyways, I've run into this problem where I need to combine certain elements in groups of three – and where each combination has to fulfill some specific criteria. The criteria themselves aren't so important, but I'm stuck on creating all the different possible combinations of elements. Possibly the number of combinations is too large for me to handle the way I plan to, so any help just calculating the number of possible combinations would be helpful as well.
Problem:
I have 360 elements that I want to divide into groups of 3 elements in each set. Each element is an actual physical component, so it can only be a part of one group. The order of elements in each group doesn't matter.
Since I have 360 elements and there is 3 elements in each group, this means that I'm making 120 groups. But there are many ways to arrange these groups. My problem is:
1. How many unique set of groups can I make? (Order of elements in groups and order of groups doesn't matter).
2. I feel there should be a fairly straight-forward algorithm to create all these possible sets of groups, yet I've twisted my brain all day long without finding out how. Any help would be much appreciated.
Example with fewer elements and lower group size:
Say I had 4 elements and was to group them in pairs. This means I would make 2 groups per set.
If I start by giving each element just an index number, then I start with the following elements: 1, 2, 3, 4
I could then group them as follows:
Set 1: (1, 2) and (3, 4)
Set 2: (1, 3) and (2, 4)
Set 3: (1, 4) and (2, 3)
Another example:
Say I have 6 elements and want to group them in triplets. This also means 2 groups per set.
So I have the following elements: 1, 2, 3, 4, 5, 6
Set 1: (1, 2, 3) and (4, 5, 6)
Set 2: (1, 2, 4) and (3, 5, 6)
Set 3: (1, 2, 5) and (3, 4, 6)
Set 4: (1, 2, 6) and (3, 4, 5)
Set 5: (1, 3, 4) and (2, 5, 6)
Set 6: (1, 3, 5) and (2, 4, 6)
Set 7: (1, 3, 6) and (2, 4, 5)
Set 8: (1, 4, 5) and (2, 3, 6)
Set 9: (1, 4, 6) and (2, 3, 5)
Set 10: (1, 5, 6) and (2, 3, 4)
But how many such sets exists if I have 360 elements to divide into groups of 3? And how do I generate the list of all those sets?
Best Answer
Oh boy, there are a lot more than you can probably imagine.
We want to pick a total of 120 groups. The first group, we must pick 3 elements out of the 360 that are there. There are $360\choose3$ ways to pick them, where $${n\choose k}=\frac{n!}{(n-k)!k!}$$
Next, we would pick the next group with $357\choose3$ ways, etc etc all the way down to $3\choose3$ ways.
The answer is the product of all of these terms, i.e., $$\prod_{n=1}^{120}{3n\choose3}$$Now, we can collapse some terms, since $k=3$ in each combination, and the numerator of each successive term cancels the denominator of the previous. So, the product equals $$\frac{360!}{120!\cdot(3!)^{120}}$$which has 671 digits. I'll post the pastebin for the whole number here. So no, you don't really want a list. You'd overload the entire earth's storage.
As a final note, if you have $n$ items and $k$ objects you want per group, (obviously $n$ is a multiple of $k$), the formula for the number of ways to group the elements is $$\frac{n!}{\frac nk!\cdot(k!)^{n/k}}$$