列表排序/修改问题
一开始，我不太确定这个问题是否适合在这里提问，但看完常见问题后，我觉得这个话题应该是可以的……而且我也不确定这算不算某种特定类型的问题（比如背包问题），所以标题有点模糊，抱歉。
不过，言归正传。为了练习Python，并且更好地理解一些编程的基本概念，我决定写一个简单的即时淘汰投票模拟。关于即时淘汰投票的描述可以在这里找到：http://en.wikipedia.org/wiki/Instant-runoff_voting
简单来说，选民通过给每个候选人分配一个数字来排名，1代表他们的第一选择，2代表第二选择，依此类推……如果投票结束时没有任何候选人获得多数票，那么得票最少的候选人就会被淘汰，投给他们的票会转给选民的第二选择候选人。
假设有五个候选人和20个选民，总共需要投100票（5x20），每一票都需要指向投票的选民和他们投给的候选人。
为了表示这些信息，我选择使用嵌套列表，这样每个子列表就代表一个选民（或选票），而子列表中的每个索引则代表一个候选人。
可视化如下：
[[1,3,2,5,4]...]
所以 ballot[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
谢谢
4 个回答
在这个过程中，任何时候一张选票都是由一个还没有被淘汰的候选人“拥有”的，而这个候选人是名字旁边写的偏好数字最小的那个。
所以，你不需要特别处理初始计数，也不需要模拟手动程序去实际重新分配被淘汰候选人的选票；只需在每个阶段进行简单的总计（重新计数）就可以了——这样逻辑会简单很多。对于一个现实的模拟来说，如果选票的数量远远大于可能的不同选票数量（N个候选人的阶乘），你可能想在开始之前把选票分成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 absurdum 来证明。你不能把选票分配给已经被淘汰的候选人。如果有候选人X比候选人Y更受这张选票的偏爱，那么你也不能把选票分配给候选人Y。因此，唯一有效的选择就是最受欢迎的未被淘汰的候选人。
关于阶乘(N)：如果有5个候选人，而有效的选票必须包含数字1,2,3,4,5的排列组合，那么就有 5! 种不同的选票——第一个候选人有5种选择，第二个候选人有4种选择，依此类推，最后一个候选人只有1种选择。5x4x3x2x1 == 5! == 120。
关于包：想象一下，有100,000张有效的选票和5个候选人。计票员设置了120个箱子，把每张选票放入相应的箱子里，同时进行计数，或者他们可能会称重每个箱子:-)，或者他们可能会对每张选票进行光学字符识别，然后用一个使用 collections.Counter 的Python脚本来处理。“包”就是“这个箱子的内容”。
这段话没有直接回答你的问题，但我写了一个非常简单的程序来计算结果。你可以在github上找到我的程序和单元测试。希望这对你有帮助。
下面的代码使用了一种暴力破解的方法（没有经过优化），但它非常可靠：
#!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模块，具体可以参考注释。
平局的情况会自动处理（所有平局的候选人都会被宣布为获胜者）。
可能的优化方法包括根据选票对选民进行分组（如果选民数量远多于选票数量），并通过重新分配输家的票数来更新计数（而不是重新进行全面的计数）。上面的实现提供了一个参考实现，可以将其结果与优化版本进行比较。:)