On Wed, 22 Aug 2018 at 17:33, Richard Damon <rich...@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 -- https://mail.python.org/mailman/listinfo/python-list