Majority Voting
December 16, 2011
There are several solutions. The easiest accumulates the counts, reports a winner if any of the counts exceeds half the available votes, and reports failure if it reaches the end of the votes without finding a winner. We use an association list to accumulate the counts, on the assumption that the number of different candidates is likely to be small, but any other dictionary structure would work equally well:
(define (majority1 xs)
(let ((goal (/ (length xs) 2)))
(let loop ((xs xs) (counts (list)))
(cond ((null? xs) #f)
((assoc (car xs) counts) =>
(lambda (x)
(let ((n (+ (cdr x) 1)))
(if (< goal n) (car x)
(loop (cdr xs) (cons (cons (car x) n) counts))))))
(else (loop (cdr xs) (cons (cons (car xs) 1) counts)))))))
Here are some examples; note that in the third example A is a plurality but not a majority:
> (majority1 '(A B A B A))
A
> (majority1 '(A A A C C B B C C C B C C))
C
> (majority1 '(A B C A B A))
#f
If the data is of some type that permits a less-than comparison, the median element is the winner, assuming that it is the majority. We reuse the select function from a previous exercise, and change our data to integers to suit the less-than function used there:
(define (majority2 xs)
(let ((goal (floor (/ (length xs) 2))))
(confirm (select goal xs) xs goal)))
Select uses shuffle and the random number generator from the Standard Prelude. We need a confirm function to check that the median value is actually the majority:
(define (confirm cand xs goal)
(let loop ((xs xs) (k 0))
(cond ((< goal k) cand)
((null? xs) #f)
((equal? cand (car xs))
(loop (cdr xs) (+ k 1)))
(else (loop (cdr xs) k)))))
Here are the same examples shown above:
> (majority2 '(1 2 1 2 1))
1
> (majority2 '(1 1 1 3 3 2 2 3 3 3 2 3 3))
3
> (majority2 '(1 2 3 1 2 1))
#f
The final algorithm is due to Robert S Boyer and J Strother Moore; it operates in O(n) time and O(1) space, and can be used on-line, for instance with data stored on magnetic tape (assuming a single rewind). The idea is to keep at all times a candidate winner, incrementing a count by 1 each time the candidate is seen, decrementing the count by 1 each time some other candidate is seen, and resetting the candidate with the current item whenever the count is zero; the surviving candidate is in the majority, if a majority exists. Boyer and Moore (the same guys that wrote the string-matching algorithm) wrote a delightful paper which not only describes the algorithm with a lot of clobbering but also describes a formal proof of their FORTRAN 77 program; we call our program mjrty because they did:
(define (mjrty zs)
(let loop ((cand #f) (k 0) (xs zs))
(cond ((null? xs)
(confirm cand zs (/ (length zs) 2)))
((zero? k)
(loop (car xs) 1 (cdr xs)))
((equal? cand (car xs))
(loop cand (+ k 1) (cdr xs)))
(else (loop cand (- k 1) (cdr xs))))))
And here are our examples one more time:
> (mjrty '(A B A B A))
A
> (mjrty '(A A A C C B B C C C B C C))
C
> (mjrty '(A B C A B A))
#f
You can run the program at http://programmingpraxis.codepad.org/CMspzByH.
Programming Praxis 
A Haskell solution: https://gist.github.com/1485531
simple solution in python:
def majority(A):
min = len(A)/2.0
counts = {}
for x in A:
if x in counts:
counts[x] += 1
else:
counts[x] = 1
a = max(counts.iteritems(), key = lambda x: x[1])
if a[1] > min:
print "The winner is:", a[0]
else:
print "There is no winner"
Sorry, thought that would work.. pastebin then:
http://pastebin.com/PQA541V2
Clojure version of the naive candidate counting using built-in “frequencies”
(defn majority [xs] (let [goal (/ (count xs) 2) xs-f (frequencies xs)] (ffirst (filter #(> (second %) goal) xs-f))))Implementation of the Boyer and Moore mjrty function
(defn mjrty [xs] (let [goal (/ (count xs) 2) pick (fn [[cand n] c] (cond (= cand c) [cand (inc n)] (zero? (dec n)) [c 1] :else [cand (dec n)])) countc (fn [cand] (reduce #(if (= cand %2) (inc %1) %1) 0 xs))] (when-let [cand (first (reduce pick [nil 1] xs))] (when (> (countc cand) goal) cand))))It may be cheating, but one of Python’s got very useful modules is
collections:#!/usr/bin/env python from collections import Counter def majority(votes): C = Counter(votes) maj = sum(C.itervalues()) / 2.0 # possibly faster than len(votes) pair = C.most_common(1)[0] return pair[0] if pair[1] > maj else None if __name__ == "__main__": print majority(['a', 'b', 'a', 'b', 'a']) print majority(['a', 'a', 'a', 'c', 'c', 'b', 'b', 'c', 'c', 'c', 'b', 'c', 'c']) print majority(['a', 'b', 'c', 'a', 'b', 'a'])My python 2.7.x solution:
from itertools import groupby maj = lambda lv: (filter(lambda x: x[1] > len(lv)/2,[(key,len(list(val))) for (key,val) in groupby(sorted(lv))]) + [('Nobody',-1)])[0][0]In order to test the above function:
And the output should be:
The data types in R are so subtle that it is no fun, but there is expressive power in there. The table-making function counts each element in the vote vector, and arranges the elements as names for the corresponding counts. The index expression compares twice each count to the total number of votes, and the resulting vector of truth values selects those names whose count makes the comparison true.
win <- function (votes) {
counts <- table(votes)
names(counts)[counts + counts > length(votes)]
}
Splitting a string results in a list that contains the result, which must then be extracted from that list. The vector of winners contains the winner if there is winner, and is empty if there is no winner.
> win(strsplit('A A A C C B B C C C B C C', ' ')[[1]])
[1] "C"
> win(strsplit('A B C A B C A', ' ')[[1]])
character(0)
void voting(char str[]){int l,ch[300],max=0,i;
char winner;
l=strlen(str);
for(i=0;i<300;i++){
ch[i]=0;
}
for(i=0;i<l;i++){
ch[str[i]]++;
}
for(i=0;imax){
max=ch[i];
winner= i;
}}
if (max>=l/2){
printf("%c is the winner in the voting with %d percentage votes",winner,max*100/l);
}
else{
printf("No one GOT MAJORITY votes");
}}
Dylan version: https://gist.github.com/1490785
A Common Lisp solution:
(defun winner (votes)
(loop
with hash = (make-hash-table)
with needed = (/ (length votes) 2)
for vote in votes
when (> (incf (gethash vote hash 0)) needed)
return vote))
? (winner ‘(A B C A A C C A))
NIL
? (winner ‘(A B C A A A C C A))
A
Opps, formating went wrong.
(defun winner (votes)
(loop
with hash = (make-hash-table)
with needed = (/ (length votes) 2)
for vote in votes
when (> (incf (gethash vote hash 0)) needed)
return vote))
? (winner ‘(A B C A A C C A))
NIL
? (winner ‘(A B C A A A C C A))
A
[/sourcecode lang]
In ruby …
def majority(l) h = Hash.new(0) l.each { |v| h[v] += 1 } max = h.max {|a,b| a[1] <=> b[1]} max[1] >= l.length / 2.0 ? "#{max[0]} won with #{max[1]} out of #{l.length} total votes" : "No winner" end v1 = %w[A A A C C B B C C C B C C] v2 = %w[A B C A B C A] puts "v1 = #{majority(v1)}" puts "v2 = #{majority(v2)}"Java version~~ https://gist.github.com/1605036
a little long compared with others. :)