다음 코드는 무력 방식 (이 최적화되지 않은)을 사용하지만, 매우 강력 :
#!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+의 collections 모듈을 사용할 수도 있습니다.
타이가 자동으로 처리됩니다 (모든 묶여진 후보자가 승자로 선언됩니다).
가능한 최적화는 가능한 투표자보다 더 많은 투표자가있는 경우 투표 용지별로 투표자를 그룹화하고 전체 재검 표를 다시하는 대신 패자의 카운트를 재배포하여 카운트를 업데이트하는 것을 포함합니다. 위의 구현은 결과를 최적화 된 버전과 비교할 수있는 참조 구현을 제공합니다. :)
오, 당신은 모든 것을 했어요 : D 덕분에 나는 정말로 노력을 기울였습니다. get_counnts 함수는 어떻게 작동합니까? – danem
@ Pete :이 답변을 승인 해 주셔서 감사합니다. 투표 용지의 첫 번째 위치에있는 후보자 수를 계산하는'get_count()'에 Python <2.7 코드를 추가했습니다. 또한 후보자가 어떤 첫 번째 위치에도 출전 할 수없고 패자로 놓칠 수없는 드문 버그를 수정했습니다. – EOL
분명히하기 위해, 이것은 유출 투표가 아닙니다. 투표 용지 ('바위', '종이', '가위', '가위', '종이', '암석')를 고려하십시오. 이 프로그램은 바위와 가위 사이의 매듭을 선포 할 것입니다. IRV에 따르면 정확한 우승자는 '종이'입니다. – dmd