For our local election hustings, someone from the audience asks a question and then the candidates take it in turns to answer it. The host decides which order the candidates should answer for each question.
There will probably be 5 candidates at the hustings, though it could be up to 7 or as few as 4.
The host wants to produce the fairest possible order for candidates to answer questions, so that one candidate doesn't answer first or last more frequently than other candidates. Also, he wants candidates to talk before and after each other with a roughly equal distribution.
(I have assigned each candidate a letter between A - E, and then candidates will draw from a hat on the night to choose their letter.)
So, for example:
- ABCDE followed by ADCBE would be bad because A starts and E finishes both times.
- ABCDE followed by ABECD would be bad because B follows A and D follows C both times.
- ABCDE followed by DCEBA would satisfy all requirements.
The number of questions is variable - could be anywhere between 4 and 15.
The host wants a reproducible process that could be audited by the electoral commission if necessary, to establish that the selection process was fair. This rules out my initial approach of "produce a random list, and then edit it manually". Performance doesn't really matter - it can take up to 10 minutes to run, on a quad-core machine with 16GB RAM.
So far I have tried:
- Just producing a random list. This tends to fail on the constraints - if I keep running it until I get a list that feels right, it fails the 'reproducible' requirement.
- Calling the
levenshteinalgorithm recursively for all combinations, and taking the ones that give the highest overall score. But with so many possible combinations, it's not possible to try all of them. It also doesn't produce great results - it lets a lot of the 'B follows A 3 times in a row' type problems.
I realise that I'm probably over-engineering the solution, but I'm interested in how I would solve this if it needed to be rock solid.