Well over 150 years ago, the Reverend Thomas Kirkman posed an interesting problem in The Ladies' and Gentlemen's Diary for 1850. The curiously-named publication was in fact a mathematical journal and, as such, Kirkman's problem was mathematical in nature.

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

It's a common scenario that happens at just about every school. Given any group of schoolgirls — say, Ashley, Beth, Celeste, Daisy, Edna, Flo, Gwen, Harriet, Ingrid, Jane, Kate, Lisa, Mary, Nadia, and Odessa — they will instinctually find a way to gossip with as many smaller groups of girls as possible, and will thereby end up with an daily ordering like follows.

Sun Mon Tue Wed Thu Fri Sat
A, F, K A, B, E B, C, F E, F, I C, E, K E, G, M K, M, D
B, G, L C, D, G D, E, H G, H, K D, F, L F, H, N L, N, E
C, H, M H, I, L I, J, M L, M, A G, I, O I, K, B O, B, H
D, I, N J, K, N K, L, O N, O, C H, J, A J, L, C A, C, I
E, J, O M, O, F N, A, G B, D, J M, N, B O, A, D F, G, J

With 15 girls, there are 455 different ways to group them in three, and we need to pick 35 (5 daily groups * 7 days) of those 455 combinations.

Bring Your Own Code

Your exercise for the day: write a function that computes an arrangement for the fifteen girls as described above. The function has no return value, but instead prints out the combination.

For added challenge:

  • Medium - add a single input (num_girls) and solve the problem for 0.5 * (num_girls-1) days, where num_girls mod 3 is 0 and num_girls mod 2 is 1.
  • Hard - compute an arranagement for 13 weeks such that no group of three is the same and no 2 girls are in the same group more than once a week

 

Post your solution in the comments if you'd like and, if you have an idea for a future Bring Your Own Code, then drop me a line.

[Advertisement] BuildMaster allows you to create a self-service release management platform that allows different teams to manage their applications. Explore how!