CODEWITHSUNDEEP
algorithmcombinatoricssolverconstraint-programmingdisjoint-sets
mezzopiano
mezzopiano

Reputation: 523

How to (efficiently) generate disjoint sets while usings pairs of elements only once?

What I would like to do is split a group of (n) items into groups of equal size (groups of size m, and for simplicity assume that there are no leftovers, i.e. n is divisible by m). Doing this multiple times, I would like to ensure that no pair of items is in the same group together twice.

To make this slightly more concrete, for building groups of two out of the six items A..F, once could partition the set five times in different ways:

The same set of items can be partitioned only once into groups of three without overlapping pairs:

(As @DavidHammen points out below, there are different ways of making the partition in this example. However, having made the partition once, there is never another, second split which keeps all pairs of items apart. That's fine -- my application doesn't need to generate all possibly ways of partitioning the set globally, one solution meeting the constraints will do)

My question, now, is this: Is there a way of doing this efficiently? Are there tricks to speed up the generation of these sets?

So, far, I've been treating this as an exact cover problem, and solving it with a backtracking algorithm (a variant of DLX). This works extremely well for pairs, but as the groups become larger the number of possibilities the algorithm has to consider explodes, and processing becomes very unwieldy.

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

Any ideas and suggestions are very welcome. Thank you very much for considering this!

Update

Ok, so this has been a while, but I spent a lot more time on this and wanted to get back to you. @david-eisenstat put me on the right path by giving me the correct search term (thank you so much!) -- I've since read quite a bit on the Social Golfer Problem.

One of the best resources that I found, that I would like to share here, is the work of Markus Triska, who discusses several approaches (and then goes on to present a very nice algorithm) in his thesis. This is highly recommended if anybody runs into a similar problem!

Upvotes: 6

Views: 648

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65458

This problem is studied under the name Social Golfer Problem. The literature has nontrivial size, but there are three main approaches:

  1. Local search methods, which can handle the cases where many pairs are not present.

  2. Complete search methods like your reduction to exact cover. From what I remember, the research here revolves around efficient methods for symmetry breaking, of which your idea of fixing the first row is probably the simplest.

  3. Mathematical constructions. When q is a prime power, there's a construction for q groups of q involving finite affine planes that's not too awful to implement. Beyond that, there are a lot of one-off constructions. The Handbook of Combinatorial Designs is probably your best bet for summarizing what's known.

Upvotes: 8

Ante
Ante

Reputation: 5448

Let n=m*k, partition has m groups with k items.

After x partitions, each item is in a group with x*(k-1) other items. After creating t-1 partitions, in next partition A can choose 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 t'th partition we need:

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

Number of possible partitions decrease with square of group length. That means, there are not too much of possible partitions :-)

I would go with some greedy approach. Store for each item set of items that are available, and create new partition by adding first available item to a group.

Upvotes: 0

Related Questions