对于我们的地方选举喧嚣，观众中有人提出一个问题，然后候选人轮流回答。主持人决定候选人应按顺序回答每个问题。
可能会有 5 名候选人参加，但最多可能有 7 人或少至 4 人。
主持人希望为候选人回答问题提供尽可能公平的顺序，以便一个候选人不会比其他候选人更频繁地回答第一个或最后一个。此外，他希望候选人在彼此之前和之后以大致相等的分布进行交谈。
(我给每个候选人分配了A-E之间的字母，然后候选人将在晚上从帽子中抽出来选择他们的字母。
因此，例如：
- ABCDE其次是ADCBE会很糟糕，因为A开始和E两次结束。
- ABCDE之后是ABECD会很糟糕，因为B跟在A后面，D跟着C两次。
- ABCDE和DCEBA将满足所有要求。
问题的数量是可变的 - 可能在 4 到 15 之间。
东道主希望有一个可重复的过程，如有必要，选举委员会可以对其进行审计，以确定选择过程是公平的。这排除了我最初的"生成随机列表，然后手动编辑"的方法。 性能并不重要 - 在具有 16GB RAM 的四核机器上运行最多可能需要 10 分钟。
到目前为止，我已经尝试过：
- 只是生成一个随机列表。这往往会在约束上失败 - 如果我继续运行它直到我得到一个感觉正确的列表，它就无法满足"可重现"的要求。
- 对所有组合递归调用
levenshtein算法，并选取总分最高的组合。但是有这么多可能的组合，不可能尝试所有的组合。它也不会产生很好的结果 - 它让很多"B 连续跟随 A 3 次"类型的问题。
我意识到我可能过度设计了解决方案，但我感兴趣的是，如果它需要坚如磐石，我将如何解决这个问题。
非常好的问题，让我思考了 10 分钟，然后才能找到一些解决方案。
我想到一种方法，我想在这里讨论。
因此，让我们举一个例子来理解我想到的方法。
Input: Candidates - [A,B,C,D,E] and 3 questions.
Step1. Let's generate all the possible combinations of the candidates,
ex:- A,B,C,D,E | A,C,B,D,E ..... D,E,B,C,A etc.
Step2. Take first string A,B,C,D,E and make use of two pointers, one
starting at beginning and other starting at the end, like this
A B C D E
^ ^
| |
Step3. So for first question our order will be like this - A,B,C,D,E
Step4. For the next question increment beginning pointer and decrement ending pointer.
Step5. So for the next question our pointers look like this
A B C D E
^ ^
| |
Step6. So out of the calculated permutations select that permutation which
has B in the starting and D in the ending.
So for the second question, our configuration would look like this
B,A,C,E,D
Step7. Increment the same starting pointer and decrement the ending pointer
in the same fashion for the next questions also.
Step8. Now when increment pointer reaches the end or decrement pointer
reaches the start then reverse them and we took A,B,C,D,E as our
string to move pointers.
Now take another string to move pointers on.
据我说，这种流程可以为回答问题提供更平等的机会分配。
这个算法可以是一个起点，我们可以更新它的某些部分以随机选择指针或字符串等。
希望这有帮助！