List sorting/modify problem

Question

Initially, I wasn't sure whether this was the appropriate place for this question, but after reading through the FAQ I feel fairly confident the topic is acceptable.... Furthermore I wasn't sure if this would be classified as a particular type of problem (eg. a knapsack problem), thus, the title is rather vague. I'm sorry for that.

Anyways. As both practice for python, and an exercise to better understand general programming concepts, I've decided to write a simple Instant-Runoff Vote simulation. A description of instant Runoff voting can be found here: http://en.wikipedia.org/wiki/Instant-runoff_voting

Basically a voter ranks each candidate by assigning them a number, one being their first choice, two being their second choice etc... If at the end of voting no single candidate has a majority the candidate with the smallest share is eliminated and the votes that went to them go to the voters second choice candidate.

Assuming that there are five candidates and 20 voters, 100 votes (5x20) need to be cast, and each vote needs to be able point to the voter that cast it, and who the vote is for.

To represent this, I chose to use a nested list so that each sublist represented a single voter (or ballot), and each index of that sublist represented a single candidate.

Visualized:

[[1,3,2,5,4]...] So ballot[0][0] is voter 1's vote for candidate 1

While I think this is a rather simple and effecient way to handle this (as far as I can tell) I am running into trouble when trying to:

a) Rank the candidates based upon the number of "1" votes they receive

b) Redistribute the votes after a candidate has been eliminated

I suppose with enough convoluted nested loops, and enough variables, I could achieve both of these, but not without the program becoming needlessly complex and confusing.

Here is the program so far...

#!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

So yeah, thats pretty much it. I'm thinking that part of my problem lies in how I choose to represent the data(in the nested lists). If anyone has any critiques and or suggestions, please share them! :D

Thanks

Answer 1

At any stage of the procedure, a ballot is "owned" by the candidate who has not been eliminated and who has the smallest preference number written against their name.

Consequently, you don't need to special-case the initial count, and you don't need to emulate the manual procedure and physically redistribute the votes of eliminated candidates; just do a brute-force total (re)count at each stage -- the logic is much simpler. For a realistic simulation, where the number of ballots is much greater than the number of possible different ballots (factorial(N=number_of_candidates)), you may wish to tally the votes into N! parcels before you start.

Pseudocode:

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)

A very strong hint: don't hard-code the number of candidates and the number of ballots; make them variable inputs to your script.

Update in response to comment

You wrote:

The fact that each ballot, at any given round of voting only effectively casts a vote for a single candidate means that I don't need to worry about any of the other listed preferences.

I'm not sure what you mean by "don't worry about". You need to examine all N preferences, ignoring the candidates that have been eliminated already, and choosing the most preferred candidate out of the remainder. Then, of course, you ignore the others; all you need to do for the "owner" candidate is results[owner] += 1.

If it's the owner determination rule that you are worried about: This can be shown to be true by reductio ad absurdum. You can't allocate the ballot to an already-eliminated candidate. You can't allocate the ballot to candidate Y if there is a candidate X who is more preferred by this ballot than candidate Y. Hence the only valid choice is the most-preferred non-eliminated candidate.

About factorial(N): If there are 5 candidates, and a valid ballot paper must have a permutation of the numbers 1,2,3,4,5 then there are 5! different possible ballots -- 5 choices for the 1st candidate, 4 for the second, ..., 1 for the 5th. 5x4x3x2x1 == 5! == 120.

About parcels: Imagine that there are 100,000 valid ballot papers and 5 candidates. The counters set up 120 bins and throw each ballot paper into the appropriate bin, counting as they go, or maybe they weigh each bin :-), or maybe they OCR each ballot and use a Python script that uses collections.Counter. "parcel" equals "contents of such a bin".

Answer 2

The following code uses a brute force approach (it is not optimized), but is quite robust:

#!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

The output goes like this (with 4 candidates):

* 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']

This code can also use the collections module from Python 2.7+, as indicated in the comment.

Ties are automatically handled (all tied candidates are declared winners).

Possible optimizations include grouping the voters by ballots (if there are many more voters than possible ballots), and updating the counts by redistributing the counts from losers (instead of redoing a full recount). The above implementation provides a reference implementation whose results can be compared to optimized versions. :)

Answer 3

What you intended to do in your loop is

shufvote = possible[:]
random.shuffle(shufvote)
ballots.append(shufvote)

Do you get what you expected with this?

The above code first copies the list of possible votes, then shuffles the copy. In fact, random.shuffle() modifies "in place" the list it is given as argument (it does not return it). Hope this helps!

Answer 4

It doesn't answer your question directly but I wrote a very simple program to calculate results. You can find my program and unit test on github. That might be useful.