# Algorithm for dividing a set of numbers into groups

by jorgendt
Tags: algorithm, dividing, groups, numbers
 Sci Advisor PF Gold P: 1,776 Firstly it is useful to count how many ways this can be done. There is a function which does this called the multinomial coefficient (generalization of the binomial coefficient). If you wish to divide a set of N objects into groups of size $n_1, n_2,\cdots , n_k$ where these $n$'s add up to big N, the number of ways is: $$\frac{N!}{n_1 !\cdot n_2 ! \cdot \ldots \cdot n_k!},\quad \text{where}\quad n!=n(n-1)(n-2)\cdots 1$$ (i.e. 5! = (5)(4)(3)(2)(1) = 120.) So the number of ways to divide 18 objectsinto 6 specific partitions of 3 each is... $$\frac{18!}{3!\cdot 3! \cdot 3! \cdot 3! \cdot 3! \cdot 3! }=... \frac{18\cdot 17 \cdot 16 \cdot 15\cdot 14\cdot 13 \cdot 12\cdot 11\cdot 10 \cdot 9 \cdot 8\cdot 7\cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6\cdot 6\cdot 6 \cdot 6\cdot 6\cdot 6} =\ldots = 137,225,088,000$$ That's if each of the 6 groups of 3 has different meaning. If however you simply want to figure ways to divide them up into sets of a given size you need to divide by the number of ways to rearrange partitions of a given size. In the above example there are 6 sets of size 3 so you divide by 6! (six factorial = 720) to get 190,590,400. Now counting is good, but if you need an algorithm to enumerate every case then that's tough especially if you want to be sure to get every case but not repeat any equivalent cases. If you simply want to picke one arrangement at random then put all elements in a list, shuffle the list thoroughly and pick the first $n_1$ of that list, the next $n_2$ of that list, ... and so on.