# How to partition a list in smaller lists so that the odds of one element encountering another element is evenly distributed?

I'm struggling with an algorithm to divide a group of contestants into smaller groups to make up rounds. Take for example a group of $20$ people, which I want to divide into $3$ groups $(7,7,6).$ For each round in a contest, the groups are different, so that everybody has to combat everybody else in a rather fair distribution.

The problem is that with a (naive) random selection one person has to combat the same person more then another one. I.e. Two elements end up often in the same group.

I would like to make this more fair so that for a given number of contestants, group size (not all groups are the same size) and number of rounds, the algorithm finds a fair set of groups per round so that on average every contestant has the same odds of meeting the same contestant during the rounds.

Is there any literature on this topic I can consult? Or any known algorithms?

• This sounds like an exercise in number theory or combinatorics rather than probability or randomness. You would only use probability if your constraints didn't fully determine what the solution was. – probabilityislogic Apr 26 '11 at 13:17
• How many rounds are there? Do the three groups compete against each other, or do the people compete against each other within the groups? – GaBorgulya Apr 26 '11 at 13:38
• The amount of rounds varies from 6 to let's say 20. It depends on the number of participants and the duration of the contest. Typically a round takes 15 minutes per group. If a contest takes 6 hours, we can have 4 groups and 6 rounds. Groups around 7 to 10 people are OK. People compete against each other. – Johan Apr 26 '11 at 13:44
• How do you mean "people compete against each other"? Could you be more specific? Taking a round with a group of 7 people does this mean that there are $7\cdot 6 / 2 = 21$ competitions run? – GaBorgulya Apr 26 '11 at 13:47
• As an example, take 20 competitors and assume we have a contest with 6 rounds. Each round consists of a different task that must be completed. The 20 competitors are divided into 3 groups: 7,7 and 6. The groups vary per round, so you do not compete against the same people all the time. This means there are 3*6 = 18 competitions run. The question is to come up with an algorithm to make this as fair as possible... – Johan Apr 26 '11 at 14:28

Consider for each pair of people the number of rounds in which they are in the same group (i.e., the number of times they play each other). We would want this multiset $S$ of numbers to consist of numbers that are close to each other. We might, for example, try to have $\max S - \min S \leq 1$ (that is, if $A$ plays $B$ $n$ times, then $C$ plays $D$ at most $n + 1$ and at least $n - 1$ times). (Caveat - at this point it is not clear to me that this is always possible.) Or we might try to have the variance of the $S$ be minimal. Finally, we could try to minimize the variance subject to the min / max condition.
If the groups would be the same size, then you might be able to use block designs to achieve perfect balance (where $S$ is constant) for some sets of parameters. Otherwise, however, I think there is no theory that gives you an exact solution to this problem. It may well be that the most practical way to solve this is using a meta-heuristic such as Simulated Annealing or Tabu Search.