列表排序/修改問題

Question

最初，我不確定這是否是適合這個問題的地方，但在閱讀完常見問題解答之後，我覺得這個主題是可以接受的。此外，我不確定是否這將被歸類爲特定類型的問題（例如揹包問題），因此標題相當模糊。我很抱歉。

反正。作爲python練習，以及更好地理解一般編程概念的練習，我已經決定編寫一個簡單的Instant-Runoff投票模擬。即時徑流投票的描述可以在這裏找到：http://en.wikipedia.org/wiki/Instant-runoff_voting

基本上，選民通過分配給他們一個號碼，一個是他們的第一選擇，兩個是他們的第二選擇等等，如果在投票結束時，單一候選人佔多數，最小份額的候選人被淘汰，並且他們的選票將被投票選舉候選人。

假設有五名候選人和20名選民，需要投100票（5x20），並且每個投票都需要能夠指向投票人和投票人。

爲了表示這一點，我選擇了使用嵌套列表，以便每個子列表代表一個選舉人（或選票），並且該子列表的每個索引代表一個候選人。

可視化：

[1,3,2,5,4] ...] 所以投票[0] [0]是選民1的投票候選1

雖然我認爲這是一個相當簡單和有效的方式來處理這個問題（據我所知），我嘗試時遇到了麻煩：

a）根據候選人的「1」票數收到

b）在候選人被淘汰之後重新分配選票

我想有足夠的複雜的嵌套循環和足夠的變量，我可以實現這兩個目標，但並非沒有程序變得不必要的複雜和混亂。

以下是節目至今...

#!usr/bin/python 

#Alt Voter Solution 3 

import random 

ballots = [] 
results = [0,0,0,0,0] 

#Generate 20 ballots. Since each ballot has 5 seperate 
#unique numbers, I felt it would be best if I just 
#shuffled a list and appended it 20 times 
for voters in range(20): 
    possible = [1,2,3,4,5] 
    for x in range(1): 
     shufvote = random.shuffle(possible) 
     ballots.append(possible) 

for cand in range(5): 
    for voter in ballots: 
     if voter[cand] == 1: 
      results[cand] +=1 

所以，是的，那是相當多了。我想我的問題的一部分在於我如何選擇表示數據（在嵌套列表中）。如果有人有任何批評和/或建議，請分享！ ：d

感謝

Answer 1

下面的代碼使用蠻力的方法（它不是最佳的），但也相當健壯：

#!usr/bin/env python 

import random 
import collections 

# Candidates: 
candidates = ['John', 'Max', 'Philip', 'Eric', 'Jane'] 

def simul_ballots(num_voters): 
    """ 
    Returns the (random) ballots of num_voters voters. 
    """ 

    ballots = [] 

    choice = candidates[:] 

    for _ in range(num_voters): 
     random.shuffle(choice) 
     ballots.append(choice[:]) # Copy 

    return ballots 

def get_counts(ballots): 
    """ 
    Returns the number of votes for each candidate placed first in the 
    ballots. 

    Candidates present in the ballots but found in any first ballot 
    places are given a count of zero. 
    """ 

    counts = dict()  
    for ballot in ballots: 
     vote = ballot[0] 
     if vote in counts: 
     counts[vote] += 1 
     else: 
     counts[vote] = 1 

    # Python 2.7+ replacement for the above code: 
    # counts = collections.Counter(ballot[0] for ballot in ballots) 

    candidates = set() 
    for ballot in ballots: 
     candidates.update(ballot) 

    for not_represented in set(candidates)-set(counts): 
     counts[not_represented] = 0 

    return counts 


def get_winners(ballots): 
    """ 
    Returns the winners in the given ballots (lists of candidates), or 
    [] if there is no winner. 

    A winner is a candidate with 50 % or more of the votes, or a 
    candidate with as many votes as all the other candidates. 
    """ 

    counts = get_counts(ballots) 

    max_count = max(counts.values()) 
    num_counts = sum(counts.values()) 

    potential_winners = [candidate for (candidate, count) in counts.items() 
         if count == max_count] 

    if max_count >= num_counts/2. or len(potential_winners) == len(counts): 
     return potential_winners 
    else: 
     return [] 


def get_losers(ballots): 
    """ 
    Returns the loser(s) of the ballots, i.e. the candidate(s) with the 
    fewest voters. 

    Returns [] if all candidates have the same number of votes. 
    """ 

    counts = get_counts(ballots) 

    min_count = min(counts.values()) 

    potential_losers = [candidate for (candidate, count) in counts.items() 
         if count == min_count] 

    if len(potential_losers) == len(counts): 
     return [] 
    else: 
     return potential_losers 

def remove_candidate(ballots, candidate): 
    """ 
    Removes the given candidate from the ballots. 
    """ 
    for ballot in ballots: 
     ballot.remove(candidate) 


if __name__ == '__main__': 

    ballots = simul_ballots(20) 

    while True: 

     print "* Votes:" 
     for ballot in ballots: 
     print '-', ballot 
     print "=> Counts:", get_counts(ballots) 

     winners = get_winners(ballots) 
     if winners: 
     break 

     # The losers are removed: 
     losers = get_losers(ballots) 
     print '=> Losers:', losers 
     for loser in losers: 
     remove_candidate(ballots, loser) 

    print "Winners: ", winners 

輸出是這樣的（帶有4個候選）：

* Votes: 
- ['Max', 'John', 'Eric', 'Philip'] 
- ['Philip', 'Max', 'Eric', 'John'] 
- ['Eric', 'Philip', 'John', 'Max'] 
- ['Philip', 'John', 'Max', 'Eric'] 
- ['Eric', 'Max', 'Philip', 'John'] 
- ['Max', 'Philip', 'John', 'Eric'] 
- ['Max', 'John', 'Eric', 'Philip'] 
- ['Eric', 'Philip', 'Max', 'John'] 
- ['Max', 'Eric', 'Philip', 'John'] 
- ['Philip', 'Max', 'Eric', 'John'] 
- ['John', 'Eric', 'Max', 'Philip'] 
- ['Philip', 'Eric', 'Max', 'John'] 
- ['Max', 'Philip', 'John', 'Eric'] 
- ['Philip', 'Max', 'John', 'Eric'] 
- ['Philip', 'Eric', 'Max', 'John'] 
- ['John', 'Philip', 'Eric', 'Max'] 
- ['John', 'Max', 'Philip', 'Eric'] 
- ['Eric', 'Philip', 'John', 'Max'] 
- ['John', 'Eric', 'Philip', 'Max'] 
- ['Philip', 'John', 'Max', 'Eric'] 
=> Counts: Counter({'Philip': 7, 'Max': 5, 'John': 4, 'Eric': 4}) 
=> Losers: ['John', 'Eric'] 
* Votes: 
- ['Max', 'Philip'] 
- ['Philip', 'Max'] 
- ['Philip', 'Max'] 
- ['Philip', 'Max'] 
- ['Max', 'Philip'] 
- ['Max', 'Philip'] 
- ['Max', 'Philip'] 
- ['Philip', 'Max'] 
- ['Max', 'Philip'] 
- ['Philip', 'Max'] 
- ['Max', 'Philip'] 
- ['Philip', 'Max'] 
- ['Max', 'Philip'] 
- ['Philip', 'Max'] 
- ['Philip', 'Max'] 
- ['Philip', 'Max'] 
- ['Max', 'Philip'] 
- ['Philip', 'Max'] 
- ['Philip', 'Max'] 
- ['Philip', 'Max'] 
=> Counts: Counter({'Philip': 12, 'Max': 8}) 
Winners: ['Philip'] 

這代碼也可以使用Python 2.7+的集合模塊，如註釋中所示。

關係自動處理（所有並列候選人被宣佈爲獲勝者）。

可能的優化包括通過選票將選民分組（如果選民數量多於可能的選票），並通過重新分配來自失敗者的計數來更新計數（而不是重新進行完整的重新計數）。上述實現提供了一個參考實現，其結果可以與優化版本進行比較。 :)

Answer 2

您打算什麼在循環做的是

shufvote = possible[:] 
random.shuffle(shufvote) 
ballots.append(shufvote) 

你得到你需要有什麼用？

上面的代碼頭份的可能投票的列表，然後慢騰騰的副本。實際上，random.shuffle()修改了它的參數列表（它不返回它）。希望這可以幫助！

Answer 3

它不直接回答你的問題，但我寫了一個非常簡單的程序來計算結果。你可以找到github我的程序和單元測試。這可能是有用的。

Answer 4

在程序的任何階段，投票都是由未被淘汰的候選人「擁有」，並且他們的名字的最小優先數是最低的。

因此，您不需要特殊處理初始計數，也不需要模擬手動過程並實際重新分配已淘汰候選人的投票;只需在每個階段進行暴力總計（重新計數） - 邏輯就簡單多了。對於一個真實的模擬，如果選票的數量遠遠大於可能的不同選票的數量（階乘（N = number_of_candidates）），那麼您可能希望將選票計入N！開始前的包裹。

僞代碼：

eliminated = set() 
For each round: 
    (1) calculate "results" by tallying the ballots as specified above 
    (2) iterate over "results" to determine the possible winner [tie-break rule?] 
    (3) if the possible winner has a majority, declare the result and exit the loop. 
    (4) iterate over results to determine the ejectee [tie-break rule?] 
    (5) eliminated.add(ejected_candidate) 

一個很強烈的暗示：不要硬編碼報考人數與選票的數量;使它們成爲腳本的可變輸入。

更新迴應置評

您寫道：

每個選票，在任何 給定的輪投票中，這一事實不僅有效 投下一票的單一候選人 意味着我不需要擔心 任何其他列出的偏好。

我不確定您的意思是「不要擔心」。您需要檢查所有N個偏好，忽略已經被淘汰的候選人，並從剩餘的候選人中選擇最優先的候選人。那麼當然你忽略了其他人;您需要爲「所有者」候選人執行的操作是results[owner] += 1。

如果是您擔心的所有者確定規則：這可以通過reductio ad adsurdum顯示爲true。您不能將投票分配給已經被淘汰的候選人。如果候選人X比這位候選人Y更有優勢，那麼你不能將候選人Y分配給候選人Y.因此，唯一有效的選擇是最優先選擇的未淘汰候選人。

關於階乘（N）：如果有5個候選人，並且有效選票必須有數字1,2,3,4,5的排列組合，那麼有5!不同的可能選票 - 5個選項第一候選人，第二候選人4，...，第五候選人1。 5x4x3x2x1 == 5！ == 120.

關於包裹：想象一下，有10萬有效的選票和5個候選人。這些櫃檯設置了120個垃圾箱，並將每張選票投入到適當的垃圾箱中，隨時計數，或者他們可以稱量每個垃圾箱:-)，或者他們可以對每個選票進行OCR並使用使用collections.Counter的Python腳本。 「包裹」等於「這種垃圾箱的內容」。