Partitioning a list

[Paul Moore]

On Wed, 22 Aug 2018 at 17:33, Richard Damon <Richard at damon-family.org> wrote:
> Paul, my understanding of the problem is that you want to create multiple divisions of the larger group into smaller groups, such that if two people are in the same group in 1 division, they never appear together in other divisions.
>
> One sample problem which I have had to solve with a similar restriction (but in my case was to minimize not eliminate repeats) was scheduling races. Say you have 9 cars you want to race in triples, and no pair of cars should ever meet twice. One option would be the following matches:
> 1,2,3; 4,5,6; 7,8,9
> 1,4,7; 2,5,8; 3,6,9
> 1,5,9; 2,6,7; 3,4,8
> 1,6,8; 2,4,9; 3,5,7
> You can show this is the most number of triples you can get out of 9, as every number has been paired with every other number once, so to create another triple, you must get a duplicate pairing.
> I don’t know of any general algorithm to generate these.

I don't know of a general algorithm for that either. What I'd do is:

1. Generate all the combinations
2. Run through them, keeping track of all pairings we've seen in
already-accepted combinations
3. If the new combination has no "already seen" pairings, yield it and
add its pairings to the set of already seen ones, otherwise skip it.

I think that gives the expected result.

Paul