Algorithm for dividing a set of numbers into groups

[jorgendt]

I'm looking for an algorithm for dividing a set of numbers into groups, and then doing it again in such a way that no numbers are in a group together more than once.

For instance if you have 18 numbers and divide them into groups of three you should be able to do this 8 times without any numbers having to be in the same group more than once. Any idea how I can do this?

This website: http://mathpages.com/home/kmath388.htm
kinda describes what I'm looking for, but I don't quite get the hang of how they do it, when I try to do something similar with other numbers I end up with repeats (I try to replicate the part where they divide 24 people into four-man-groups in seven different ways).

Thanks in advance for any help. :)

 

[jambaugh]

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! }=...<br /> \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}<br /> =\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.

 

[pbuk]

There is no generalised algorithm as that page (and others on this problem such as this one and http://www.maa.org/editorial/mathgames/mathgames_08_14_07.html) hint at.

If you can't use the already-generated solutions on those pages you are going to need to build some method of spanning possible combinations either with brute force or some evaluation/backtracking algorithm.