And The Winner Is …
November 26, 2013
A ballot will be a list of candidates, in order from most preferred to least preferred; an election will be a list of ballots. Counting the ballots is a composition of map, sort, and uniq-c:
(define (count ballots)
(uniq-c char=? (sort char<? (map car ballots))))
The other auxiliary function that we need removes the loser from all ballots:
(define (delete loser ballots)
(map (lambda (b) (remove loser b)) ballots))
Now we are ready to perform a runoff. First we count the ballots, then count the votes, and compute the winner (with the most votes) and the loser (with the fewest votes). If the winner has more than half the total votes, the runoff ends with a winner, otherwise the loser is removed from all the ballots and the process repeats:
(define (runoff ballots)
(let* ((num (length ballots))
(counts (count ballots))
(winner (apply maximum-by (lambda (x y) (< (cdr x) (cdr y))) counts))
(loser (apply maximum-by (lambda (x y) (< (cdr y) (cdr x))) counts)))
(if (< (/ num 2) (cdr winner)) (car winner) (runoff (delete (car loser) ballots)))))
As an example, let’s consider voting for the best motion picture of all time, from the five candidates Citizen Kane, Casablanca, The Godfather, Gone with the Wind, and Lawrence of Arabia (those are the top five from the American Film Institute, don’t blame me). First, we make a weighted list of choices:
(define choices '(("KANE" 22) ("CASA" 21) ("GODF" 20) ("WIND" 19) ("LAWR" 18)))
Then we make a random ballot based on the weighted choices:
(define (rand-ballot choices)
(define (choice choices)
(let* ((total (sum (map cadr choices))) (r (randint total)))
(let loop ((upto 0) (choices choices))
(if (< r (+ upto (cadar choices))) (car choices)
(loop (+ upto (cadar choices)) (cdr choices))))))
(let loop ((choices choices) (ballot (list)))
(if (null? (cdr choices))
(reverse (map car (cons (car choices) ballot)))
(let ((c (choice choices)))
(loop (remove c choices) (cons c ballot))))))
Then we create n ballots:
(define (vote n choices)
(let loop ((n n) (ballots (list)))
(if (zero? n)
(string-append "And the winner is ... " (runoff ballots))
(loop (- n 1) (cons (rand-ballot choices) ballots)))))
And finally we hold an election:
> (vote 1000 choices)
And the winner is ... KANE
We used sum, uniq-c, remove, maximum-by and random numbers from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/qWOmysuW.
Programming Praxis 
In Python.
from collections import Counter def runoff(votes): """every vote is a ranking from high to low e.g.: ("charles", "john", "peter", "william") """ counter = Counter(v[0] for v in votes) cand, nr_votes = counter.most_common(1)[0] if nr_votes > len(votes) // 2: return cand cand, nr_votes = counter.most_common()[-1] for v in votes: v.remove(cand) return runoff(votes)I did not think about the possibillity, that there may be more than 1 loser. In this version all losers are removed. Also, there is not always a winner. This happens quite frequently if the number of votes is low.
from collections import Counter def runoff(votes): """every vote is a ranking from high to low e.g.: ["charles", "john", "peter", "william"] If more candidates have minimum votes, remove them all """ if not votes or len(votes[0]) == 0: return "no winner" counts = Counter(v[0] for v in votes).most_common() cand, nr_votes = counts[0] if nr_votes > len(votes) // 2: return cand loser, loser_votes = counts[-1] #print counts for p, v in reversed(counts): if v == loser_votes: for v in votes: v.remove(p) return runoff(votes)