5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I think there are some details where you're enforcing too strong a constraint. In particular, you seem to be restricting to sequences of 4 playdates, which isn't going to allow every child to be in a group with every other child of the same gender if there are 6 or more children of each gender. $\endgroup$
    – Peter Taylor
    Commented Apr 6, 2019 at 12:59
  • $\begingroup$ Thanks a lot for your reply, Peter Taylor! The idea is for the playdate groups to run across school years: i.e. in 1st grade the first two lists of 4-tuples only will be "used". In 2nd grade the following two lists of 4-tuples will be used etc. Does this make sense? Thanks Again for any help I can get... $\endgroup$
    – Thomas Juul Eriksen
    Commented Apr 7, 2019 at 10:26
  • $\begingroup$ No, I'm afraid it doesn't make sense. I thought the groups changed every month? Doesn't a grade last nine or ten months? On a separate issue, I have some thoughts but nowhere near enough to write an answer. You now have enough rep to participate in chat. Might it be worth creating a chat room dedicated to this question? I'm happy to set it up if you're interested. $\endgroup$
    – Peter Taylor
    Commented Apr 7, 2019 at 16:59
  • $\begingroup$ Hi again, Peter! I would be delighted to engage in a chat around this, as I am quite determined to get this solved. Just for clarification: There is one playdate in each group per month. Four kids in each group means that the groups change every four months. Thanks again for your kind support!! $\endgroup$
    – Thomas Juul Eriksen
    Commented Apr 9, 2019 at 7:42
  • $\begingroup$ Chat room. $\endgroup$
    – Peter Taylor
    Commented Apr 9, 2019 at 9:14

0

Reset to default

You must log in to answer this question.