Rearrangement of groups such that no two members meet again

Suppose that we are given $n$ groups of $m$ people. We want to rearrange these $nm$ people into the same format of $n$ groups of $m$ with that the catch that any two people who were originally in a group together cannot be rearranged in the same group. How many ways can we rearrange the groups? It appears that this question is related to derangements but quite a bit more generalized.

A possibly related problem is the maximum number of times these rearrangements can happen before two previously encountered partners must meet again.

I am not sure if there is an elementary solution to these problems. It would appear that the first problem at least should be quite common in combinatorics and so I wonder if it is the special case of a famous problem.

Solution 1:

Problems of this sort have been of interest for a long time. Perhaps the earliest was Kirkman's schoolgirl problem from 1850: "Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast."

The general problem, given $mn$ people, how many days can you group them into $n$ groups of $m$ so that no two people are in the same group more than once, is not easy and not completely solved. One search term that may get you somewhere is "combinatorial designs".

Solution 2:

I've recently stumbled upon this problem and it seems like the general case has not yet been solved and is referred to as a Social Golfer Problem (SGP)

The computational complexity of the SGP is currently unknown. Some instances are easily solved using construction methods from design theory, but such methods are typically restricted to certain families of instances. However, from a result derived by Colbourn in (Colbourn 1984), one can show that the completion problem of the SGP, i.e., deciding whether a partially filled schedule can be completed to conflict-free one, is NP-complete.