在選舉中對響應者的順序進行排序的算法

Question

對於我們當地的選舉限制，聽衆中有人提出一個問題，然後候選人輪流回答。主持人決定候選人應該爲每個問題回答的順序。

有可能會是在hustings 5​​名候選人，儘管它可能高達7或儘可能少的4

主機要生產最公平的順序對考生回答問題，讓一個候選人不比其他候選人回答第一或最後更頻繁。另外，他希望考生前後交談，大致平均分配。

（我已經指定各候選人A之間的信 - E，然後考生將帽子借鑑晚上來選擇他們的信。）

因此，舉例來說：

• ABCDE其次是ADCBE會很糟糕，因爲A開始並且E完成兩次。
• ABCDE後跟ABECD會很糟糕，因爲B跟隨A和D跟隨C兩次。
• ABCDE後跟DCEBA將滿足所有要求。

的問題的數量是可變的 - 第4和第15

之間的主機想要一個可重複的過程，可以由選舉委員會在必要時進行審覈，以確定該選擇過程是公平的可以在任何地方。這排除了我的「產生一個隨機列表，然後手動編輯它」的最初方法。性能並不重要 - 在具有16GB RAM的四核機器上運行最長可能需要10分鐘。

到目前爲止，我曾嘗試：

• 就產生一個隨機列表。這往往會因爲約束而失敗 - 如果我繼續運行它，直到我得到一個感覺正確的列表，它就無法達到「可重現」的要求。
• 對所有組合遞歸調用levenshtein算法，並採用給出最高總分的算法。但是有這麼多可能的組合，不可能嘗試所有這些組合。它也不會產生很好的結果 - 它讓很多'B連續3次'出現類型問題。

我意識到我可能過度設計解決方案，但是我對如何解決這個問題感興趣，如果它需要堅如磐石的話。

Answer 1

非常好的問題，讓我思考了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. 

根據我這個流程可以給出更平均的回答問題的機會分配。

這種算法可能是一個起點，我們就可以更新它的某些部分隨機選擇的指針或字符串等

希望這有助於！