Majority Voting
December 16, 2011
In an election, the winner is required to have the majority of the votes. For instance, with the set of votes {A A A C C B B C C C B C C}, the winner is C with 7 of 13 votes. Some elections have no winner; with the set of votes {A B C A B C A}, A gets a plurality of the votes but not a majority, so there is no winner. You can think of voting as a political election, or as redundant hardware in a critical system where a failure of one component must not lead to failure of the overall system.
Your task is to write a function that determines the winner of a vote, or indicates that no candidate reached a majority. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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. :)