Being an organised sort of person (and a sucker who can't say no), I tend to do a lot of the admin and paperwork for the house I share with a few friends. One of the things I do is draw up the chores rota. I've typically done it like this*:

Week      10/09 17/09 24/09 ...
Bathroom  Tom   David Harry ...
Kitchen   Dick  Tom   David ...
Bins      Harry Dick  Tom   ...
Hoovering David Harry Dick  ...

Careful and studious readers will have no difficulty in spotting the pattern.

Inevitably, though, instead of being grateful for the minutes I slaved over my desk putting this together, t'housemates complained. Specifically, Tom complained that 'I always do something the week after Dick's supposed to have done it, and he makes a mess of everything'.

Given the choice between speaking to Dick to correct the problem, or writing some code, I wrote some code which starts with the above layout, then shuffles the columns until the following constraints are satisfied:

  • A given person never does the same thing two weeks running
  • For any given pair of people (p1, p2), this pair never appears twice in a given row

Careful and studious readers (with Maths or CS degrees) will have no difficulty working out the number of weeks of chores rota I've limited myself to doing at a time, becuse the constraints become impossible for a greater number.

* No, my housemates aren't really called Tom, Dick and Harry. After five years at an all-boys school, there's no way I'd live in an all-male household.