python - 列表排序/修改问题

Question

最初，我不确定这是否适合这个问题，但在通读了常见问题解答后，我确信这个主题是可以接受的......此外，我不确定这是否会被归类为特定类型的问题(例如背包问题)，因此标题相当模糊。对此我感到很抱歉。

无论如何。作为 python 的实践和更好地理解一般编程概念的练习，我决定编写一个简单的即时决选投票模拟。即时径流投票的描述可以在这里找到:http://en.wikipedia.org/wiki/Instant-runoff_voting

基本上，选民通过给每个候选人分配一个数字来对他们进行排名，一个是他们的第一选择，两个是他们的第二选择等......如果在投票结束时没有一个候选人获得多数票，则淘汰份额最小的候选人投给他们的选票将投给选民的第二选择候选人。

假设有 5 名候选人和 20 名选民，需要投 100 票 (5x20)，并且每票都需要能够指向投出它的选民，以及投给谁的票。

为了表示这一点，我选择使用嵌套列表，以便每个子列表代表一个选民(或选票)，并且该子列表的每个索引代表一个候选人。

可视化:

[[1,3,2,5,4]...] So ballot[0][0] is voter 1's vote for candidate 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+ 中的集合模块，如注释中所示。

平局是自动处理的(所有平局的候选人都被宣布为获胜者)。

可能的优化包括按选票对选民进行分组(如果选民比可能的选票多得多)，以及通过重新分配失败者的计票来更新计票(而不是重新进行全面重新计票)。上述实现提供了一个引用实现，其结果可以与优化版本进行比较。 :)