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.

About these ads

Pages: 1 2

2 Responses to “And The Winner Is …”

  1. Paul said

    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)
    
  2. Paul said

    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: