Subversion Repositories Remote Hare Voting

Rev

Rev 24 | Rev 40 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 24 Rev 39
Line 25... Line 25...
25 
import sys
 25 
import sys
26 
import math
26 
import math
27 
import random
 27 
import random
28 
 
 28 
 
29 
fTrace = 1
 29 
fTrace = 1
- 
 
 30 
randcalls = 0
30 
 
 31 
 
31 
def trace(s):
 32 
def trace(s):
32 
    global fTrace
 33 
    global fTrace
33 
    if fTrace: print s
 34 
    if fTrace: print s
34 
    return
 35 
    return
35 
 
 36 
 
36 
def findWinner(winners, losers, tally, quota, nWinners):
 37 
def findWinner(winners, losers, tally, quota, nWinners):
- 
 
 38 
    global randcalls
- 
 
 39 
    cWin = quota       # number of votes for highest winner
- 
 
 40 
    lWin = []          # list of candidates with highest votes
37 
    for candidate in tally.keys():
 41 
    for c in tally.keys():
38 
        if candidate not in winners and len(tally[candidate]) >= quota:
 42 
        if c not in losers and c not in winners and len(tally[c]) >= cWin:
- 
 
 43 
            if len(tally[c]) == cWin:
- 
 
 44 
                lWin.append(c)
- 
 
 45 
            else:
- 
 
 46 
                lWin = [c]
- 
 
 47 
                cWin = len(tally[c])
- 
 
 48 
    if len(lWin) == 1:
39 
            return candidate
 49 
        return lWin[0]
- 
 
 50 
    elif len(lWin) > 1:
- 
 
 51 
        trace("\tselecting winning candidate randomly from %s" % lWin)
- 
 
 52 
        randcalls += 1
- 
 
 53 
        return random.choice(lWin)
40 
 
 54 
 
41 
    # Check to see if only enough candidates remain
 55 
    # Check to see if only enough candidates remain
42 
    n = 0
 56 
    n = 0
43 
    last = ""
 57 
    last = ""
44 
    for candidate in tally.keys():
 58 
    for candidate in tally.keys():
Line 48... Line 62...
48 
    if nWinners - len(winners) >= n:
 62 
    if nWinners - len(winners) >= n:
49 
        return last
 63 
        return last
50 
    return
 64 
    return
51 
 
 65 
 
52 
def redistributeWinner(winner, winners, losers, tally, quota):
 66 
def redistributeWinner(winner, winners, losers, tally, quota):
- 
 
 67 
    global randcalls
53 
    excess = len(tally[winner]) - quota
 68 
    excess = len(tally[winner]) - quota
54 
    if excess <= 0:
 69 
    if excess <= 0:
55 
        trace("\tno excess ballots to redistribute")
 70 
        trace("\tno excess ballots to redistribute")
56 
    else:
 71 
    else:
57 
        trace("\tredistributing %d excess ballot(s) at random from %s" %
 72 
        trace("\tredistributing %d excess ballot(s) at random from %s" %
58 
              (excess, winner))
 73 
              (excess, winner))
59 
        while len(tally[winner]) > quota:
 74 
        while len(tally[winner]) > quota:
60 
            i = int(random.uniform(0, len(tally[winner])))
 75 
            i = int(random.uniform(0, len(tally[winner])))
- 
 
 76 
            randcalls += 1
61 
            trace("\trandom choice = ballot %d" % (i+1))
 77 
            trace("\trandom choice = ballot %d" % (i+1))
62 
            ballot = tally[winner][i]
 78 
            ballot = tally[winner][i]
63 
            tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
 79 
            tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
64 
            redistributeBallot(ballot, winner, winners, losers, tally)
 80 
            redistributeBallot(ballot, winner, winners, losers, tally)
65 
    traceTally(quota, tally)
 81 
    traceTally(quota, tally)
Line 74... Line 90...
74 
            break
 90 
            break
75 
    if ballot:
 91 
    if ballot:
76 
        trace("\tineffective ballot dropped: %s" % ballot)
 92 
        trace("\tineffective ballot dropped: %s" % ballot)
77 
 
 93 
 
78 
def findLoser(losers, winners, tally):
 94 
def findLoser(losers, winners, tally):
- 
 
 95 
    global randcalls
79 
    cMin = sys.maxint  # least number of votes for candidate loser
 96 
    cMin = sys.maxint  # least number of votes for candidate loser
80 
    lMin = []          # list of candidates with least votes
 97 
    lMin = []          # list of candidates with least votes
81 
    for c in tally.keys():
 98 
    for c in tally.keys():
82 
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
 99 
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
83 
            if len(tally[c]) == cMin:
 100 
            if len(tally[c]) == cMin:
84 
                lMin.append(c)
 101 
                lMin.append(c)
85 
            else:
 102 
            else:
86 
                lMin = [c]
 103 
                lMin = [c]
87 
                cMin = len(tally[c])
 104 
                cMin = len(tally[c])
88 
    trace("\nELIMINATING LOW CANDIDATE RANDOMLY FROM %s" % lMin)
 - 
 
89 
    if len(lMin) == 0:
 105 
    if len(lMin) == 0:
90 
        return None
 106 
        return None
- 
 
 107 
    elif len(lMin) == 1:
- 
 
 108 
        return lMin[0]
91 
    else:
 109 
    else:
- 
 
 110 
        trace("\teliminating low candidate randomly from %s" % lMin)
- 
 
 111 
        randcalls += 1
92 
        return random.choice(lMin)
 112 
        return random.choice(lMin)
93 
 
 113 
 
94 
def redistributeLoser(loser, losers, winners, tally, quota):
 114 
def redistributeLoser(loser, losers, winners, tally, quota):
95 
    excess = len(tally[loser])
 115 
    excess = len(tally[loser])
96 
    if excess <= 0:
 116 
    if excess <= 0:
Line 122... Line 142...
122 
#   else:
 142 
#   else:
123 
#       eliminate lowest ranking candidate
 143 
#       eliminate lowest ranking candidate
124 
#       redistribute wasted votes to next priority candidate
 144 
#       redistribute wasted votes to next priority candidate
125 
#
 145 
#
126 
def dotally(nWinners, ballots):
 146 
def dotally(nWinners, ballots):
- 
 
 147 
    global randcalls
127 
    nBallots = len(ballots)
 148 
    nBallots = len(ballots)
128 
    quota = int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
 149 
    quota = int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
129 
 
 150 
 
130 
    trace("INPUT SUMMARY")
 151 
    trace("INPUT SUMMARY")
131 
    trace("\t%d ballots" % nBallots)
 152 
    trace("\t%d ballots" % nBallots)
Line 159... Line 180...
159 
                trace("\nELIMINATED: %s" % loser)
 180 
                trace("\nELIMINATED: %s" % loser)
160 
                redistributeLoser(loser, losers, winners, tally, quota)
 181 
                redistributeLoser(loser, losers, winners, tally, quota)
161 
            else:
 182 
            else:
162 
                trace("Not enough chosen candidates to fill all positions")
 183 
                trace("Not enough chosen candidates to fill all positions")
163 
                break
 184 
                break
- 
 
 185 
    trace("\nNumber of random choices made: %d" % randcalls)
164 
 
 186 
 
165 
    return winners
 187 
    return winners
166 
 
 188