At my kids' school, the kids are meeting in playdate groups of two girls and two boys every month. The groups are constructed to get as much variation in the groups over the months. Having seen too many cases of either of my kids getting paired up with the same one or two kids months in a row, I set my mind to making a small (F#) program that given a list of girls' names and a list of boys' names would output a list of lists of 4-tuples. A 4-tuple corresponds to a playdate group for four months (one playdate per kid per month). Each list of 4-tuples corresponds to a complete set of playdate groups for a four months' period. The list of lists is the smallest set of playdate group set ensuring "complete variation". This proved a LOT harder then expected!
I have qualified my "complete variation" expectation in the following requirements:
- In every list of groups, each kid is present in exactly one group
- Each kid shall be in a playdate group with every other kid of same gender at least once and at most twice
- Each boy (girl, resp.) shall be in a group with every girl at least once, but as few times as possible
- For two consecutive lists of groups the number of same kids being in group together shall be as small as possible
For a list of boys (a,b,c,d) and girls (A,B,C,D), a solution is: [[(a,b,A,B), (c,d,C,D)], [(a,c,A,C), (b,d,B,D)], [(a,d,B,C), (b,c,A,D)], [(a,b,C,D), (c,d,A,B)]]
This is done totally by hand and my problem is what a general algorithm would look like. Any ideas?
I have made a function (based on the round-robin algorithm) that given a list of names, constructs the list of unique 2-tuples (e.g., for the example above: [a,b,c,d] --> [(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)]), but I am not sure whether this is useful in solving my problem. The algorithm will eventually need to check that each of these combinations is matched by at least one group, but is there a need to generate the tuples up front.
My intention here is fully altruistic! I would like to make a solution that all parents can utilise free of charge and the code will be published on GitHub! Any help is greatly appreciated!!
Thanks -- Thomas