通用技术 分享一个有趣的算法题

flystar · September 13, 2019 · 376 hits

请注意,第二偏好投票并不总是确保获胜的候选人获得大多数选民的支持

  • 在本例中,我们可以应用多轮重新分配,每次都将选票最少的候选人的剩余首选项重新分配给其他候选人
  • 我们一直这样做,直到一个候选人获得绝对多数,或者只剩下两个候选人

如前所述,如果有两个或两个以上得票最低的候选人拥有相同数量的已分配选票,那么如果您比较他们的名字,则重新分配器名字低于另一个名字的候选人
注:当重新分配选票时,如果该候选人已经重新分配,则下一个首选项可能不再可用,因此我们直接进入下面的首选项
多选择投票方案的例子
候选人:a, b, c, d, e
考虑一个有5个投票人的选民
选票情况:(a, b, c, d, e)、(b, e, d, c, a)、(c, d, e, b, a)、(d, b, a, c, e)、(e, a, c, b, d)
基于优先选择的每个候选人的票数: a: 1, b: 1, c: 1, d: 1, e: 1。没有一个候选人拥有绝对多数。在相等的最低候选选项中,‘a’的名称按顺序排在第一位,所以将‘a’的选票重新分配给下一个候选人b:
b: (b, e, d, c, a)、(b, c, d, e)-> 该选票来自于a
c: (c, d, e, b, a)
d: (d, b, a, c, e)
e: (e, a, c, b, d)
在这一轮过去后,还是没有候选人获得绝对多数选票。在相等的最低候选项(c, d, e)中,‘c’的名称的顺序排序是第一个,所以将‘c’的选票重新分配给下一个优先候选人d:
b: (b, e, d, c, a)、(b, c, d, e)
d: (d, b, a, c, e)、(d, e, b, a)-> 该选票来自于c
e: (e, a, c, b, d)
还是没有候选人获得绝对多数,此时e是得票最少的候选人,将e的选票重新分配给下一个优先候选人,因为此时a和c已经被淘汰了,所以是b:
b: (b, e, d, c, a)、(b, c, d, e)、(b, d)-> 该选票来自于e
d: (d, b, a, c, e)、(d, e, b, a)
此时候选人b获得了绝对多数选票,所以赢得选举!
编写一个函数mutiple_preference(votes),该函数使用多个首选项投票方案返回给定投票列表的选举结果

  • 一个投票列表,其中每个投票都是按优先顺序递减的候选人对应的字符串列表。返回一个字符串,其中包含使用首选项投票获得最多选票的候选人的名单,如果出现平局,则返回一个字符串'tie'

假设:
* 没有候选人的名字是'tie'
* 每个选票包含所以候选人,而且每个候选人在每个选票中只出现一次

下面是一些调用函数的例子:

>>> v1 = [["a", "b", "c", "d", "e"], ["b", "e", "d", "c", "a"], ["c", "d", "e", "b", "a"], ["d", "b", "a", "c", "e"], ["e", "a", "c", "b", "d"]]
>>> multiple_preference(v1)
'b'
>>> v2 = [["a", "b", "c", "d", "e"], ["b", "e", "d", "c", "a"], ["c", "d", "e", "b", "a"], ["d", "b", "a", "c", "e"], ["d", "a", "b", "c", "e"], ["e", "a", "c", "b", "d"]]
>>> multiple_preference(v2)
'tie'

附上自己的方案

def mutiple_preference(v):
''''多选择投票方案
思路:1.候选人获胜条件:获得绝对多数的票,即总票数除以2再加1;如果最后剩下两位候选人并且票数相同,则打平
2.候选人得票情况使用字典去存储;每一轮得票最低的并且按姓名排序的候选人,将其加入过滤名单,用列表存储
3.对字典按值的长度(值即得票情况)进行排序,然后做获胜判断,无人获胜的话,取字典第一条数据,将key(即候选人名字)
加入到过滤名单(表示对应的候选人被淘汰),然后循环处理其得票情况(需要将其得票重新分配给顺位候选人,该候选人可能
有多张选票),即取每一张选票和过滤名单的差集,并还原其原来的顺序(集合是无序的,集合操作会打乱选票候选人顺位)
从而得出顺位候选人,并将该选票加入到其选票情况中(即加入到字典值中),最后删除key
4.循环对字典进行如上操作,直到满足获胜条件退出
'''
mid_votes = len(v) // 2

votes = {}
for vote in v: votes.setdefault(vote[0], []).append(vote)

losers = []

while True:
# 默认字典是按键排序,按这里对该字典的要求是按优先选择的得票数来排序并且保持该顺序,所以使用了OrderedDict
votes = OrderedDict(sorted(votes.items(), key=lambda d: len(d[1])))

# 判断是否有候选人获得绝对多数选票
the_winner = list(votes.keys())[-1]
if len(votes.get(the_winner)) >= mid_votes + 1:
return the_winner

# 判断是否有打平的情况(有且只有两位候选人,各自获得一半票),即假设字典只剩下了两条数据,并且值(列表长度)相同
if len(votes) == 2:
candidate1, candidate2 = votes.keys()
if len(votes.get(candidate1)) == len(votes.get(candidate2)) == mid_votes:
return 'tie'

# 否则取第一条数据操作
key = list(votes.keys())[0]
losers.append(key)
votes_detail = votes.get(key)
for vote_detail in votes_detail:
# 将该选票中已经淘汰掉的候选人清除,并保证选票中候选人相对位置不变,更新选票,然后添加到新的顺位候选人选票池中
update_vote_detail = sorted(list(set(vote_detail).difference(set(losers))), key=vote_detail.index)
votes.setdefault(update_vote_detail[0], []).append(update_vote_detail)
votes.pop(key)
No Reply at the moment.
需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up