Subversion Repositories Local Hare Voting

Rev

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

Rev 60 Rev 61
Line 19... Line 19...
19 
##
 19 
##
20 
## To download the complete source distribution, use Subversion:
 20 
## To download the complete source distribution, use Subversion:
21 
##
 21 
##
22 
##      % svn co http://www.bikmort.com/hare
 22 
##      % svn co http://www.bikmort.com/hare
23 
##
 23 
##
24 
## $Id: tally.py 60 2007-09-22 13:58:59Z jtkorb $
 24 
## $Id: tally.py 61 2007-09-23 22:17:14Z jtkorb $
25 
 
 25 
 
26 
import sys
 26 
import sys
27 
import math
27 
import math
- 
 
 28 
import copy
28 
import random
 29 
import random
29 
 
 30 
 
30 
fdOut = None
 31 
fdOut = None
31 
fTrace = 1
 32 
fTrace = 1
32 
randcalls = 0
 - 
 
33 
 
 33 
 
34 
class Universe:
 34 
class Universe:
35 
    id = 0                              # id of last created Universe
 35 
    id = 0                              # id of last created Universe
36 
    pendingUniverses = []
 36 
    pendingUniverses = []
- 
 
 37 
    results = {}
- 
 
 38 
    dropped = 0
- 
 
 39 
 
- 
 
 40 
    def __reset(self):
- 
 
 41 
	Universe.id = 0
37 
    completedUniverses = []
 42 
 	Universe.pendingUniverses = []
- 
 
 43 
	Universe.results = {}
- 
 
 44 
	Universe.dropped = 0
- 
 
 45
38 
 
 46 
 
39 
    def __init__(self, p, nWinners, nBallots, quota):
 47 
    def __init__(self, p, nWinners, nBallots, quota):
- 
 
 48 
	if p == 1.0:
- 
 
 49 
	    self.__reset()
40 
        Universe.id += 1
 50 
        Universe.id += 1
41 
        self.id = Universe.id
 51 
        self.id = Universe.id
- 
 
 52 
 
42 
        self.p = p
 53 
        self.p = p
43 
        self.nBallots = nBallots
 - 
 
44 
	self.nWinners = nWinners
 54 
	self.nWinners = nWinners
- 
 
 55 
        self.nBallots = nBallots
45 
        self.quota = quota
 56 
        self.quota = quota
- 
 
 57 
 
46 
        self.winners = []
 58 
        self.winners = []
47 
        self.losers = []
 59 
        self.losers = []
48 
        self.tally = {}
 60 
        self.tally = {}
49 
 
 61 
 
- 
 
 62 
	self.pendingItem = None
- 
 
 63 
	self.pendingType = None
- 
 
 64 
	self.pendingData = None
- 
 
 65 
 
50 
    def forkPendingWinners(self, lWin):
 66 
    def forkPendingWinners(self, lWin):
51 
	return self.__forkPendingList(lWin, "winner")
 67 
	return self.__forkPendingList(lWin, "winner")
52 
 
 68 
 
53 
    def forkPendingLosers(self, lMin):
 69 
    def forkPendingLosers(self, lMin):
54 
	return self.__forkPendingList(lMin, "loser")
 70 
	return self.__forkPendingList(lMin, "loser")
55 
 
 71 
 
56 
    def forkPendingRedist(self, lRedist):
 72 
    def forkPendingRedist(self, lRedist, winner):
57 
	return self.__forkPendingList(lRedist, "redist")
 73 
	return self.__forkPendingList(lRedist, "redist", winner)
58 
 
 74 
 
59 
    def __forkPendingList(self, lItems, pendingType):
 75 
    def __forkPendingList(self, lItems, type, data=None):
- 
 
 76 
        if len(lItems) == 1:
- 
 
 77 
	    return lItems[0]
- 
 
 78 
	if self.p/len(lItems) < 1.0/10000:
- 
 
 79 
	    trace("\tpassing on %d universes (p = %f)" % (len(lItems)-1, self.p/len(lItems)))
- 
 
 80 
	    Universe.dropped += len(lItems)-1
- 
 
 81 
	    return random.choice(lItems)
60 
	self.p /= len(lItems)
 82 
	self.p /= len(lItems)
- 
 
 83 
	trace("\tcreating %d universes (p = %f)" % (len(lItems)-1, self.p))
61 
	for item in lItems[1:]:
 84 
	for item in lItems[1:]:
62 
	    u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
 85 
	    u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
63 
	    u.winners = self.winners[:]
 86 
	    u.winners = self.winners[:]
64 
	    u.losers = self.losers[:]
 87 
	    u.losers = self.losers[:]
65 
	    u.tally = self.tally.copy()
 88 
	    u.tally = copy.deepcopy(self.tally)
66 
	    u.pending = item
 89 
	    u.pendingItem = item
67 
	    u.pendingType = pendingType
 90 
	    u.pendingType = type
- 
 
 91 
	    u.pendingData = data
68 
	    Universe.pendingUniverses.append(u)
 92 
	    Universe.pendingUniverses.append(u)
69 
	return lItems[0]
 93 
	return lItems[0]
70 
 
 94 
 
71 
def combinations(l, n):
 95 
def combinations(l, n):
72 
    assert(n >= 0)
 - 
 
73 
    if n == 0:
 96 
    if n == 0:
74 
	yield []
 97 
	return [[]]
75 
    else:
 98 
    else:
- 
 
 99 
        lResult = []
76 
	for i in range(len(l)):
 100 
	for i in range(len(l)):
77 
	    for lsub in combinations(l[i+1:], n-1):
 101 
	    for lsub in combinations(l[i+1:], n-1):
78 
		yield [l[i]] + lsub
 102 
		lResult.append([l[i]] + lsub)
- 
 
 103 
        return lResult
79 
 
 104 
 
80 
def trace(s):
 105 
def trace(s):
81 
    global fTrace, fdOut
 106 
    global fTrace, fdOut
82 
    if fTrace: print >>fdOut, s
 107 
    if fTrace: print >>fdOut, s
83 
    return
 108 
    return
84 
 
 109 
 
85 
def findNextWinner(u):
 110 
def findNextWinner(u):
86 
    global randcalls
 - 
 
87 
    cWin = u.quota	# number of votes for highest winner
 111 
    cWin = u.quota	# number of votes for highest winner
88 
    lWin = []		# list of candidates with highest votes
 112 
    lWin = []		# list of candidates with highest votes
89 
    for c in u.tally.keys():
 113 
    for c in u.tally.keys():
90 
        if c not in u.losers and c not in u.winners and len(u.tally[c]) >= cWin:
 114 
        if c not in u.losers and c not in u.winners and len(u.tally[c]) >= cWin:
91 
            if len(u.tally[c]) == cWin:
 115 
            if len(u.tally[c]) == cWin:
Line 96... Line 120...
96 
    if len(lWin) > 0:
 120 
    if len(lWin) > 0:
97 
        return u.forkPendingWinners(lWin)
 121 
        return u.forkPendingWinners(lWin)
98 
 
 122 
 
99 
    # Check to see if only enough candidates remain
 123 
    # Check to see if only enough candidates remain
100 
    ## TODO: sort by len(tally[c]) to choose larger winners first
 124 
    ## TODO: sort by len(tally[c]) to choose larger winners first
101 
    ## randomize and count if some with equal votes
 125 
    ## create multiple universes if some have equal votes
102 
    n = 0
 126 
    n = 0
103 
    last = ""
 127 
    last = ""
104 
    for c in u.tally.keys():
 128 
    for c in u.tally.keys():
105 
        if c not in u.winners and c not in u.losers:
 129 
        if c not in u.winners and c not in u.losers:
106 
            last = c
 130 
            last = c
Line 110... Line 134...
110 
            u.quota)
 134 
            u.quota)
111 
        return last
 135 
        return last
112 
    return
 136 
    return
113 
 
 137 
 
114 
def redistributeWinner(winner, u):
 138 
def redistributeWinner(winner, u):
115 
    global randcalls
 - 
 
116 
    excess = len(u.tally[winner]) - u.quota
 139 
    excess = len(u.tally[winner]) - u.quota
117 
    if excess <= 0:
 140 
    if excess <= 0:
118 
        trace("\tno excess ballots to redistribute")
 141 
        trace("\tno excess ballots to redistribute")
119 
    else:
 142 
    else:
120 
        lEffective = gatherEffectiveBallots(winner, u)
 143 
        lEffective = gatherEffectiveBallots(winner, u)
121 
        nRedistribute = min(excess, len(lEffective))
 144 
        nRedist = min(excess, len(lEffective))
122 
        trace("\tredistributing %d effective of %d excess ballot(s) at random from %s" %
 145 
	trace("\tredistributing %d effective ballots, %d at a time" % (len(lEffective), nRedist))
123 
              (nRedistribute, excess, winner))
 - 
 
124 
 
 - 
 
125 
## LEFT OFF HERE...
 - 
 
126 
## 	Need to create (len(lEffective) choose nRedistribute)-1 universes.
 - 
 
127 
##  	One solution is to set self.nRedistribute, then forkPendingRedist the lEffective ballots.
 - 
 
128 
## 	Must wind up with nRedistribute ballots redistributed in current universe.
 - 
 
129 
## 	u.forkPendingRedist(lEffective)
 - 
 
130 
 
 - 
 
131 
        for ballot in random.sample(lEffective, nRedistribute):
 146 
	for ballot in u.forkPendingRedist(combinations(lEffective, nRedist), winner):
132 
            randcalls += 1
 - 
 
133 
            trace("\trandom choice = %s" % ballot)
 - 
 
134 
            u.tally[winner].remove(ballot)
 147 
            u.tally[winner].remove(ballot)
135 
            redistributeBallot(ballot, u)
 148 
            redistributeBallot(ballot, u)
136 
            nRedistribute -= 1
 - 
 
137 
    traceTally(u)
 149 
    traceTally(u)
138 
 
 150 
 
139 
def gatherEffectiveBallots(winner, u):
 151 
def gatherEffectiveBallots(winner, u):
140 
    lEffective = []
 152 
    lEffective = []
141 
    for ballot in u.tally[winner]:
 153 
    for ballot in u.tally[winner]:
Line 155... Line 167...
155 
            break
 167 
            break
156 
    if ballot:
 168 
    if ballot:
157 
        trace("\tineffective ballot dropped: %s" % ballot)
 169 
        trace("\tineffective ballot dropped: %s" % ballot)
158 
 
 170 
 
159 
def findNextLoser(u):
 171 
def findNextLoser(u):
160 
    global randcalls
 - 
 
161 
    cMin = sys.maxint  # least number of votes for candidate loser
 172 
    cMin = sys.maxint  # least number of votes for candidate loser
162 
    lMin = []          # list of candidates with least votes
 173 
    lMin = []          # list of candidates with least votes
163 
    for c in u.tally.keys():
 174 
    for c in u.tally.keys():
164 
        if c not in u.losers and c not in u.winners and len(u.tally[c]) <= cMin:
 175 
        if c not in u.losers and c not in u.winners and len(u.tally[c]) <= cMin:
165 
            if len(u.tally[c]) == cMin:
 176 
            if len(u.tally[c]) == cMin:
Line 203... Line 214...
203 
#   else:
 214 
#   else:
204 
#       eliminate lowest ranking candidate
 215 
#       eliminate lowest ranking candidate
205 
#       redistribute wasted votes to next priority candidate
 216 
#       redistribute wasted votes to next priority candidate
206 
#
 217 
#
207 
def dotally(nWinners, ballots):
 218 
def dotally(nWinners, ballots):
208 
    global randcalls
 - 
 
209 
    randcalls = 0
 - 
 
210 
 
 - 
 
211 
    nBallots=len(ballots)
 219 
    nBallots=len(ballots)
212 
    quota=int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
 220 
    quota=int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
213 
 
 221 
 
214 
    u = Universe(1.0, nWinners, nBallots, quota)
 222 
    u = Universe(1.0, nWinners, nBallots, quota)
215 
 
 223 
 
Line 249... Line 257...
249 
    candidates.sort()
 257 
    candidates.sort()
250 
    for c in candidates:
 258 
    for c in candidates:
251 
        trace("\t%-16s%3d\t%3d\t%4d" % (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
 259 
        trace("\t%-16s%3d\t%3d\t%4d" % (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
252 
    traceTally(u)
 260 
    traceTally(u)
253 
 
 261 
 
254 
    continueTally(u)
 262 
    Universe.pendingUniverses.append(u)
255 
    return u.winners
 - 
 
256 
 
 263 
 
- 
 
 264 
    while len(Universe.pendingUniverses) > 0:
- 
 
 265 
    	u = Universe.pendingUniverses.pop()
- 
 
 266 
	trace("POPPED UNIVERSE %d (p = %f, %d pending):" %
- 
 
 267 
	    (u.id, u.p, len(Universe.pendingUniverses)))
- 
 
 268 
 
257 
def continueTally(u):
 269 
	if u.pendingType == "redist":
- 
 
 270 
	    trace("\tredistributing %d ballots" % len(u.pendingItem))
- 
 
 271 
	    winner = u.pendingData
258 
    while len(u.winners) < u.nWinners:
 272 
	    assert(winner in u.winners)
- 
 
 273 
	    for ballot in u.pendingItem:
- 
 
 274 
                u.tally[winner].remove(ballot)
- 
 
 275 
                redistributeBallot(ballot, u)
- 
 
 276 
        elif u.pendingType == "winner":
- 
 
 277 
	    trace("\tfinishing pending winner %s" % u.pendingItem)
259 
        winner = findNextWinner(u)
 278 
	    winner = u.pendingItem
260 
        if winner:
 279 
	    assert(winner not in u.winners)
261 
            u.winners.append(winner)
 280 
            u.winners.append(winner)
262 
            trace("\nSELECTION #%d: %s" % (len(u.winners), winner))
 281 
            trace("\nSELECTION #%d: %s" % (len(u.winners), winner))
263 
            redistributeWinner(winner, u)
 282 
            redistributeWinner(winner, u)
- 
 
 283 
	elif u.pendingType == "loser":
- 
 
 284 
	    trace("\tfinishing pending loser %s" % u.pendingItem)
- 
 
 285 
	    loser = u.pendingItem
- 
 
 286 
            u.losers.append(loser)
- 
 
 287 
            trace("\nELIMINATED: %s" % loser)
- 
 
 288 
            redistributeLoser(loser, u)
- 
 
 289 
 
264 
        else:
 290 
        u.pendingType = None
- 
 
 291 
 
- 
 
 292 
        while len(u.winners) < u.nWinners:
265 
            loser = findNextLoser(u)
 293 
            winner = findNextWinner(u)
266 
            if loser:
 294 
            if winner:
267 
                u.losers.append(loser)
 295 
                u.winners.append(winner)
268 
                trace("\nELIMINATED: %s" % loser)
 296 
                trace("\nSELECTION #%d: %s" % (len(u.winners), winner))
269 
                redistributeLoser(loser, u)
 297 
                redistributeWinner(winner, u)
270 
            else:
 298 
            else:
- 
 
 299 
	        loser = findNextLoser(u)
- 
 
 300 
                if loser:
- 
 
 301 
                    u.losers.append(loser)
- 
 
 302 
                    trace("\nELIMINATED: %s" % loser)
- 
 
 303 
                    redistributeLoser(loser, u)
- 
 
 304 
                else:
271 
                trace("Not enough chosen candidates to fill all positions")
 305 
                    trace("Not enough chosen candidates to fill all positions")
272 
                break
 306 
                    break
- 
 
 307 
 
- 
 
 308 
	winners = str(u.winners)
- 
 
 309 
	trace("RESULTS FOR UNIVERSE %d (p = %f): %s" % (u.id, u.p, winners))
- 
 
 310 
	if winners not in Universe.results: Universe.results[winners] = 0.0
- 
 
 311 
	Universe.results[winners] += u.p
- 
 
 312 
 
273 
    trace("\nNumber of random choices made: %d" % randcalls)
 313 
    trace("\nDropped %d universes with low probability" % Universe.dropped)
- 
 
 314 
    lWinners = []
- 
 
 315 
    for winner in Universe.results.keys():
- 
 
 316 
	lWinners.append("%f: %s" % (Universe.results[winner], winner))
- 
 
 317 
    lWinners.sort()
- 
 
 318 
    lWinners.reverse()
- 
 
 319 
    return lWinners