Find all possible partitions of n elements with k-sized subsets, where two elements share same set only once

Question

I have n elements that need to be partitioned into x sets, each set has to hold exactly k=4 elements.

I need to find all possible partitions with the constraint that each pair of elements only shares the same set once.

So if I start with [1 2 3 4] [5 6 7 8] [...], all consecutive partitions cannot hold e.g. [1 2 X X] or [X X 1 3]. sets are unordered.

Close to this problem are the stirling numbers of the second kind. However, they only solve the problem for arbitrarily sized sets.

Example: I have 32 mice that can be put in 8 cages, 4 per cage. The mice should be rotated between the cages in a fashion that they never meet another mouse twice. How often can you do this and what are the configurations?

Answer 1

Your problem statement ("all possible partitions") is confusing.

Let's fix the terms (if you agree) : a partition (p) is a particular (and complete) distribution of the n elements in x boxes, each with k=4 elements. (I use the term 'box' instead of 'set' to avoid confusion) (BTW, notice that, if we accept this definition, then you must restate your phrase about "consecutive partitions", it does not make sense).

Then, let´s call P ={p1,p2 ...} the set of all possible partitions. Now, we are interested in some subsets of P (we might call each of them a "proper set of partitions"). A PSOF is a set of partitions that has the given property: there are no two partitions that map the same pair of elements to the same box. (We can also add the property of being maximal: it's not possible to add another partition without violating the rule).

Now, it's not clear if you want to:

• Count how many partitions (at most) can have one of those PSOF (it's not clear for me if every PSOF has the same cardinality - probably)
• An algorithm to find the partitions of one of those PSOF.
• Count how many PSOF are.
• An algorithm to find all possible PSOF with the partitions of each one.

None seems easy to me. (Sorry, I know this is not an aswer but a clarification, but it didnt fit in the comments)

Answer 2

This is an instance of the "social golfer problem." Warwick Harvey used to have a page (http://www.cs.st-andrews.ac.uk/~wh/golf/) with a bunch of solutions for different problem sizes, but it seems to be down. The answer in your case turns out to be 10 rotations, but I don't know what the actual configurations are. Here is a 9-rotation solution, though: http://www.cs.st-andrews.ac.uk/~ianm/CSPLib//prob/prob010/solution

It is an unsolved problem for general n and k.