Проблема сортировки / изменения списка

В следующем коде используется подход грубой силы (он не оптимизирован), но достаточно прочен:

#!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+, как указано в комментарии.

Связи автоматически обрабатываются (все назначенные кандидаты объявляются победителями).

Возможные оптимизации включают группировку избирателей бюллетенями (если число избирателей превышает количество возможных избирательных бюллетеней), а также обновление подсчетов путем перераспределения счетов от неудачников (вместо повторного пересчета). Вышеупомянутая реализация обеспечивает ссылочную реализацию, результаты которой можно сравнить с оптимизированными версиями.:)