From: Benjamin Mako Hill Date: Fri, 3 Mar 2006 01:44:54 +0000 (+0000) Subject: Added support for instant run-off voting with a patch from X-Git-Url: https://projects.mako.cc/source/rubyvote/commitdiff_plain/863282d853f14245e6b494a5556e98e461b856cb?ds=sidebyside Added support for instant run-off voting with a patch from Alexis Darrasse . Thanks Alexis! git-svn-id: svn://rubyforge.org/var/svn/rubyvote/trunk@6 1440c7f4-e209-0410-9a04-881b5eb134a8 --- diff --git a/lib/runoff.rb b/lib/runoff.rb new file mode 100644 index 0000000..f9edc5e --- /dev/null +++ b/lib/runoff.rb @@ -0,0 +1,90 @@ +require 'election' + +class InstantRunoffVote < ElectionVote + def initialize(votes=nil) + @candidates = Array.new + votes.each do |vote| + @candidates = vote.uniq if vote.uniq.length > candidates.length + end + super(votes) + @candidates.each do |candidate| + @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate) + end + end + + def result + InstantRunoffResult.new(self) + end + + protected + def tally_vote(vote) + votecopy = vote.dup + candidate = votecopy.shift + votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate) + votes[candidate][0] += 1 + if votes[candidate][1].has_key?(votecopy) + votes[candidate][1][votecopy] += 1 + else + votes[candidate][1][votecopy] = 1 + end + end + + def verify_vote(vote=nil) + vote.instance_of?( Array ) and + vote == vote.uniq + end +end + +class InstantRunoffResult < ElectionResult + attr_reader :ranked_candidates + + def initialize(voteobj=nil) + unless voteobj and voteobj.kind_of?( InstantRunoffVote ) + raise ArgumentError, "You must pass an InstantRunoffVote array.", caller + end + super(voteobj) + + votes = @election.votes.clone + candidates = @election.candidates + majority = votes.inject(0) {|n, value| n + value[1][0]}/2 + 1 + @ranked_candidates = Array.new() + ranked_candidates = Array.new() + + loop do + ranked_candidates = votes.sort do |a, b| + b[1][0] <=> a[1][0] + end.collect {|i| i[0]} + @winners = ranked_candidates.find_all do |i| + votes[i][0] >= majority + end + + loser = ranked_candidates[-1] + break if self.winner? or votes[loser][0] == votes[ranked_candidates[-2]][0] + + @ranked_candidates.unshift(loser) + runoff(votes, loser) + end + @ranked_candidates.unshift(*ranked_candidates) + end + + def runoff(votes, loser) + votes.each_pair do |candidate, morevotes| + hash = morevotes[1] + hash.each_pair do |vote, count| + hash.delete(vote) + vote.delete(loser) + hash[vote] = count + end + end + votes[loser][1].each_pair do |vote, count| + candidate = vote.shift + votes[candidate][0] += count + if votes[candidate][1].has_key?(vote) + votes[candidate][1][vote] += count + else + votes[candidate][1][vote] = count + end + end + votes.delete(loser) + end +end diff --git a/test.rb b/test.rb index 3be4176..f87e41d 100755 --- a/test.rb +++ b/test.rb @@ -21,6 +21,7 @@ require 'election' require 'condorcet' require 'positional' +require 'runoff' def print_winner(result) if not result.winner? @@ -128,6 +129,60 @@ def approval_test1 print_winner( ApprovalVote.new(vote_array).result ) end +def runoff_test1 + puts "USING RUNOFF..." + puts "The winner shold be: A" + + vote_array = Array.new + 142.times {vote_array << "ABCD".split("")} + 26.times {vote_array << "BCDA".split("")} + 15.times {vote_array << "CDBA".split("")} + 17.times {vote_array << "DCBA".split("")} + + print_winner( InstantRunoffVote.new(vote_array).result ) +end + +def runoff_test2 + puts "USING RUNOFF..." + puts "The winner shold be: D" + + vote_array = Array.new + 42.times {vote_array << "ABCD".split("")} + 26.times {vote_array << "BCDA".split("")} + 15.times {vote_array << "CDBA".split("")} + 17.times {vote_array << "DCBA".split("")} + + print_winner( InstantRunoffVote.new(vote_array).result ) +end + +def runoff_test3 + puts "USING RUNOFF..." + puts "The winner shold be: C" + + vote_array = Array.new + 42.times {vote_array << "ABCD".split("")} + 26.times {vote_array << "ACBD".split("")} + 15.times {vote_array << "BACD".split("")} + 32.times {vote_array << "BCAD".split("")} + 14.times {vote_array << "CABD".split("")} + 49.times {vote_array << "CBAD".split("")} + 17.times {vote_array << "ABDC".split("")} + 23.times {vote_array << "BADC".split("")} + 37.times {vote_array << "BCDA".split("")} + 11.times {vote_array << "CADB".split("")} + 16.times {vote_array << "CBDA".split("")} + 54.times {vote_array << "ADBC".split("")} + 36.times {vote_array << "BDCA".split("")} + 42.times {vote_array << "CDAB".split("")} + 13.times {vote_array << "CDBA".split("")} + 51.times {vote_array << "DABC".split("")} + 33.times {vote_array << "DBCA".split("")} + 39.times {vote_array << "DCAB".split("")} + 12.times {vote_array << "DCBA".split("")} + + print_winner( InstantRunoffVote.new(vote_array).result ) +end + condorcet_test1() ssd_test1() ssd_test2() @@ -135,4 +190,6 @@ ssd_test3() borda_test1() plurality_test1() approval_test1() - +runoff_test1() +runoff_test2() +runoff_test3()