How to (efficiently) generate disjoint sets while element pairs are used only once?

Question

What I would like to do is divide the group (n) of elements into groups of equal size (groups of size m, and for simplicity we assume that there are no residues, i.e. n is divided by m). By doing this several times , I would like to make sure that there are no pairs of elements in the same group together twice .

To make this a little more specific, to create groups of two of the six elements of A..F , you can split the set five times in different ways once:

• (A, B) , (C, D) , (E, F)
• (A, C) , (B, E) , (D, F)
• (A, D) , (B, F) , (C, E)
• (A, E) , (B, D) , (C, F)
• (A, F) , (B, C) , (D, E)

The same set of elements can only be divided once into groups of three without overlapping pairs:

• (A, B, C) , (D, E, F)

_{(As @DavidHammen points out below, there are different ways to create a section in this example. However, once you make a section, there will never be another, second separation that will separate all pairs of elements. Excellent - my application should not generate all possible ways to split the set around the world, one solution that meets the limits)}

---

Now my question is: is there a way to do this effectively? Are there any tricks to speed up the generation of these sets?

So, yes, I saw this as an exact cover problem and solving it using the backtracking algorithm (DLX option). This works very well for couples, but as the groups get larger, the number of possibilities that the algorithm has to consider explodes and the processing becomes very cumbersome.

What I'm looking for is tricks to speed things up . Any ideas are very welcome, in particular (but not limited to):

• Optimization and heuristic in order to reduce the number of possibilities that need to be considered before solving (for example, from the above examples it can be seen that the first split can be done arbitrarily, and the first set of each section [the first column above] can be generated automatically).
• Are there any retreat options that can handle a huge number of candidates? (i.e. no need to create all the features in advance)
• Other algorithms , suitable or mathematical concepts that I should consider?

Any ideas and suggestions are very welcome. Thank you very much for your attention!

---

Update

Okay, so it has been a while, but I spent much more time on it and wanted to get back to you. @ david-eisenstat set me on the right track by giving me the correct search query (thank you so much!). Since then I read a little about the problem of the social player.

One of the best resources that I have found that I would like to share here is the work of Marcus Trisk , who discusses several approaches (and then continues to present a very good algorithm) in his thesis. This is highly recommended if someone is facing a similar problem!

Answer 1

This issue is being studied under the name The Social Problem of Golfers . Literature is non-trivial in size, but there are three main approaches:

• Local search methods that can handle cases where many pairs are not present.

• Complete search methods, such as your reduction to the exact cover. From what I remember, the research here revolves around effective symmetry breaking techniques, of which your idea of ​​fixing the first line is probably the easiest.

• Mathematical constructions. When q is a simple power, there exists a construction for q groups of q that includes finite affine planes that are not too terrible to implement. In addition, there are many disposable designs. A guide to combinatorial projects is probably the best way to help you summarize what is known.

Answer 2

Let n=m*k , the section has m groups with elements k .

After x sections, each element is in a group with x*(k-1) other elements. After creating the t-1 partitions in the next section, A can be selected for:

 second element : n - (t-1)*(k-1) - 1 items third element : n - 2*(t-1)*(k-1) - 2 items fourth element : n - 3*(t-1)*(k-1) - 3 items ... k'th element : n - (t-1)*(k-1)^2 - (k-1) items 

To create the t'th section, we need:

 n - (t-1)*(k-1)^2 - (k-1) > 0 => t < (n - k + 1) / ((k-1)^2) + 1 

The number of possible partitions decreases with the squared group length. This means that there are not many possible sections :-)

I would go with some greedy approach. Save the set of available elements for each element and create a new section by adding the first available element to the group.