Subversion Repositories Remote Hare Voting

Rev

Rev 75 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 75 Rev 78
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 75 2009-01-08 23:29:13Z jtkorb $
 24 
# $Id: tally.py 78 2016-05-11 19:18:03Z jtkorb $
25 
 
 25 
 
26 
import sys
 26 
import sys
27 
import math
27 
import math
28 
import copy
 28 
import copy
29 
import random
 29 
import random
Line 38... Line 38...
38 
    pendingUniverses = []
 38 
    pendingUniverses = []
39 
    results = {}
 39 
    results = {}
40 
    dropped = 0
 40 
    dropped = 0
41 
 
 41 
 
42 
    def __reset(self):
 42 
    def __reset(self):
43 
	Universe.id = 0
 43 
        Universe.id = 0
44 
 	Universe.pendingUniverses = []
 44 
        Universe.pendingUniverses = []
45 
	Universe.results = {}
 45 
        Universe.results = {}
46 
	Universe.dropped = 0
 46 
        Universe.dropped = 0
47
47 
 
48 
 
 48 
 
49 
    def __init__(self, p, nWinners, nBallots, quota):
 49 
    def __init__(self, p, nWinners, nBallots, quota):
50 
	if p == 1.0:
 50 
        if p == 1.0:
51 
	    self.__reset()
 51 
            self.__reset()
52 
        Universe.id += 1
 52 
        Universe.id += 1
53 
        self.id = Universe.id
 53 
        self.id = Universe.id
54 
 
 54 
 
55 
        self.p = p
 55 
        self.p = p
56 
	self.nWinners = nWinners
 56 
        self.nWinners = nWinners
57 
        self.nBallots = nBallots
 57 
        self.nBallots = nBallots
58 
        self.quota = quota
 58 
        self.quota = quota
59 
 
 59 
 
60 
        self.winners = []
 60 
        self.winners = []
61 
        self.losers = []
 61 
        self.losers = []
62 
        self.tally = {}
 62 
        self.tally = {}
63 
 
 63 
 
64 
	self.pendingItem = None
 64 
        self.pendingItem = None
65 
	self.pendingType = None
 65 
        self.pendingType = None
66 
	self.pendingData = None
 66 
        self.pendingData = None
67 
 
 67 
 
68 
    def forkPendingWinners(self, lWin):
 68 
    def forkPendingWinners(self, lWin):
69 
	return self.__forkPendingList(lWin, "winner")
 69 
        return self.__forkPendingList(lWin, "winner")
70 
 
 70 
 
71 
    def forkPendingLosers(self, lMin):
 71 
    def forkPendingLosers(self, lMin):
72 
	return self.__forkPendingList(lMin, "loser")
 72 
        return self.__forkPendingList(lMin, "loser")
73 
 
 73 
 
74 
    def forkPendingRedist(self, lRedist, winner):
 74 
    def forkPendingRedist(self, lRedist, winner):
75 
	return self.__forkPendingList(lRedist, "redist", winner)
 75 
        return self.__forkPendingList(lRedist, "redist", winner)
76 
 
 76 
 
77 
    def __forkPendingList(self, lItems, type, data=None):
 77 
    def __forkPendingList(self, lItems, type, data=None):
78 
	global fParallel
 78 
        global fParallel
79 
 
 79 
 
80 
        if len(lItems) == 1:
 80 
        if len(lItems) == 1:
81 
	    return lItems[0]
 81 
            return lItems[0]
82 
	if not fParallel:
 82 
        if not fParallel:
83 
	    trace(1, "\tmaking random choice among %d alternatives" %
83 
            trace(1, "\tmaking random choice among %d alternatives" %
84 
		len(lItems))
 84 
                len(lItems))
85 
	    return random.choice(lItems)
 85 
            return random.choice(lItems)
86 
 
 86 
 
87 
	# Split into parallel universes unless too many with small probability
 87 
        # Split into parallel universes unless too many with small probability
88 
	#
 88 
        #
89 
	if Universe.id > 10000 and self.p/len(lItems) < 1.0/10000:
 89 
        if Universe.id > 10000 and self.p/len(lItems) < 1.0/10000:
90 
	    trace(1, "\tpassing on %d universes (p = %f)" %
90 
            trace(1, "\tpassing on %d universes (p = %f)" %
91 
		(len(lItems)-1, self.p/len(lItems)))
 91 
                (len(lItems)-1, self.p/len(lItems)))
92 
	    trace(1, "\tmaking random choice among %d alternatives" %
92 
            trace(1, "\tmaking random choice among %d alternatives" %
93 
		len(lItems))
 93 
                len(lItems))
94 
	    Universe.dropped += len(lItems)-1
 94 
            Universe.dropped += len(lItems)-1
95 
	    return random.choice(lItems)
 95 
            return random.choice(lItems)
96 
 
 96 
 
97 
	self.p /= len(lItems)
 97 
        self.p /= len(lItems)
98 
	trace(1, "\tcreating %d universes (p = %f)" % (len(lItems)-1, self.p))
 98 
        trace(1, "\tcreating %d universes (p = %f)" % (len(lItems)-1, self.p))
99 
 
 99 
 
100 
	for item in lItems[1:]:
 100 
        for item in lItems[1:]:
101 
	    u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
 101 
            u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
102 
	    u.winners = self.winners[:]
 102 
            u.winners = self.winners[:]
103 
	    u.losers = self.losers[:]
 103 
            u.losers = self.losers[:]
104 
	    u.tally = copy.deepcopy(self.tally)
 104 
            u.tally = copy.deepcopy(self.tally)
105 
	    u.pendingItem = item
 105 
            u.pendingItem = item
106 
	    u.pendingType = type
 106 
            u.pendingType = type
107 
	    u.pendingData = data
 107 
            u.pendingData = data
108 
	    Universe.pendingUniverses.append(u)
 108 
            Universe.pendingUniverses.append(u)
109 
	return lItems[0]
 109 
        return lItems[0]
110 
 
 110 
 
111 
def combinations(l, n):
 111 
def combinations(l, n):
112 
    if n == 0:
 112 
    if n == 0:
113 
	return [[]]
 113 
        return [[]]
114 
    else:
 114 
    else:
115 
        lResult = []
 115 
        lResult = []
116 
	for i in range(len(l)):
 116 
        for i in range(len(l)):
117 
	    for lsub in combinations(l[i+1:], n-1):
 117 
            for lsub in combinations(l[i+1:], n-1):
118 
		lResult.append([l[i]] + lsub)
 118 
                lResult.append([l[i]] + lsub)
119 
        return lResult
 119 
        return lResult
120 
 
 120 
 
121 
def trace(t, s):
 121 
def trace(t, s):
122 
    global traceLevel, fdOut
 122 
    global traceLevel, fdOut
123 
    if traceLevel >= t: print >>fdOut, s
 123 
    if traceLevel >= t: print >>fdOut, s
Line 156... Line 156...
156 
    if excess <= 0:
 156 
    if excess <= 0:
157 
        trace(1, "\tno excess ballots to redistribute")
 157 
        trace(1, "\tno excess ballots to redistribute")
158 
    else:
 158 
    else:
159 
        lEffective = gatherEffectiveBallots(winner, u)
 159 
        lEffective = gatherEffectiveBallots(winner, u)
160 
        nRedist = min(excess, len(lEffective))
 160 
        nRedist = min(excess, len(lEffective))
161 
	trace(1, "\tredistributing %d effective ballots, %d at a time" %
161 
        trace(1, "\tredistributing %d effective ballots, %d at a time" %
162 
	    (len(lEffective), nRedist))
 162 
            (len(lEffective), nRedist))
163 
	for ballot in u.forkPendingRedist(combinations(lEffective, nRedist), winner):
 163 
        for ballot in u.forkPendingRedist(combinations(lEffective, nRedist), winner):
164 
            u.tally[winner].remove(ballot)
 164 
            u.tally[winner].remove(ballot)
165 
            redistributeBallot(ballot, u)
 165 
            redistributeBallot(ballot, u)
166 
    traceTally(1, u)
 166 
    traceTally(1, u)
167 
 
 167 
 
168 
def gatherEffectiveBallots(winner, u):
 168 
def gatherEffectiveBallots(winner, u):
Line 274... Line 274...
274 
    trace(0, "\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
 274 
    trace(0, "\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
275 
    candidates = totalMrk.keys()
 275 
    candidates = totalMrk.keys()
276 
    candidates.sort()
 276 
    candidates.sort()
277 
    for c in candidates:
 277 
    for c in candidates:
278 
        trace(0, "\t%-16s%3d\t%3d\t%4d" %
278 
        trace(0, "\t%-16s%3d\t%3d\t%4d" %
279 
	    (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
 279 
            (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
280 
    traceTally(0, u)
 280 
    traceTally(0, u)
281 
 
 281 
 
282 
    Universe.pendingUniverses.append(u)
 282 
    Universe.pendingUniverses.append(u)
283 
 
 283 
 
284 
    while len(Universe.pendingUniverses) > 0:
 284 
    while len(Universe.pendingUniverses) > 0:
285 
    	u = Universe.pendingUniverses.pop()
 285 
        u = Universe.pendingUniverses.pop()
286 
	trace(1, "POPPED UNIVERSE %d (p = %f, %d pending):" %
286 
        trace(1, "POPPED UNIVERSE %d (p = %f, %d pending):" %
287 
	    (u.id, u.p, len(Universe.pendingUniverses)))
 287 
            (u.id, u.p, len(Universe.pendingUniverses)))
288 
 
 288 
 
289 
	if u.pendingType == "redist":
 289 
        if u.pendingType == "redist":
290 
	    trace(1, "\tredistributing %d ballots" % len(u.pendingItem))
 290 
            trace(1, "\tredistributing %d ballots" % len(u.pendingItem))
291 
	    winner = u.pendingData
 291 
            winner = u.pendingData
292 
	    assert(winner in u.winners)
 292 
            assert(winner in u.winners)
293 
	    for ballot in u.pendingItem:
 293 
            for ballot in u.pendingItem:
294 
                u.tally[winner].remove(ballot)
 294 
                u.tally[winner].remove(ballot)
295 
                redistributeBallot(ballot, u)
 295 
                redistributeBallot(ballot, u)
296 
        elif u.pendingType == "winner":
 296 
        elif u.pendingType == "winner":
297 
	    trace(1, "\tfinishing pending winner %s" % u.pendingItem)
 297 
            trace(1, "\tfinishing pending winner %s" % u.pendingItem)
298 
	    winner = u.pendingItem
 298 
            winner = u.pendingItem
299 
	    assert(winner not in u.winners)
 299 
            assert(winner not in u.winners)
300 
            u.winners.append(winner)
 300 
            u.winners.append(winner)
301 
            trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
 301 
            trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
302 
            redistributeWinner(winner, u)
 302 
            redistributeWinner(winner, u)
303 
	elif u.pendingType == "loser":
 303 
        elif u.pendingType == "loser":
304 
	    trace(1, "\tfinishing pending loser %s" % u.pendingItem)
 304 
            trace(1, "\tfinishing pending loser %s" % u.pendingItem)
305 
	    loser = u.pendingItem
 305 
            loser = u.pendingItem
306 
            u.losers.append(loser)
 306 
            u.losers.append(loser)
307 
            trace(1, "\nELIMINATED: %s" % loser)
 307 
            trace(1, "\nELIMINATED: %s" % loser)
308 
            redistributeLoser(loser, u)
 308 
            redistributeLoser(loser, u)
309 
 
 309 
 
310 
        u.pendingType = None
 310 
        u.pendingType = None
Line 314... Line 314...
314 
            if winner:
 314 
            if winner:
315 
                u.winners.append(winner)
 315 
                u.winners.append(winner)
316 
                trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
 316 
                trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
317 
                redistributeWinner(winner, u)
 317 
                redistributeWinner(winner, u)
318 
            else:
 318 
            else:
319 
	        loser = findNextLoser(u)
 319 
                loser = findNextLoser(u)
320 
                if loser:
 320 
                if loser:
321 
                    u.losers.append(loser)
 321 
                    u.losers.append(loser)
322 
                    trace(1, "\nELIMINATED: %s" % loser)
 322 
                    trace(1, "\nELIMINATED: %s" % loser)
323 
                    redistributeLoser(loser, u)
 323 
                    redistributeLoser(loser, u)
324 
                else:
 324 
                else:
325 
                    trace(1, "Not enough chosen candidates to fill all positions")
 325 
                    trace(1, "Not enough chosen candidates to fill all positions")
326 
                    break
 326 
                    break
327 
 
 327 
 
328 
	winners = str(u.winners)
 328 
        winners = str(u.winners)
329 
	if fParallel:
 329 
        if fParallel:
330 
	    trace(1, "RESULTS FOR UNIVERSE %d (p = %f): %s" % (u.id, u.p, winners))
 330 
            trace(1, "RESULTS FOR UNIVERSE %d (p = %f): %s" % (u.id, u.p, winners))
331 
	if winners not in Universe.results: Universe.results[winners] = 0.0
 331 
        if winners not in Universe.results: Universe.results[winners] = 0.0
332 
	Universe.results[winners] += u.p
 332 
        Universe.results[winners] += u.p
333 
 
 333 
 
334 
    if fParallel:
 334 
    if fParallel:
335 
	trace(0, "\nTracked %d alternative decisions (skipped %d with low probability)" %
 335 
        trace(0, "\nTracked %d alternative decisions (skipped %d with low probability)" %
336 
	    (Universe.id, Universe.dropped))
 336 
            (Universe.id, Universe.dropped))
337 
 
 337 
 
338 
    trace(0, "\nFINAL RESULTS")
 338 
    trace(0, "\nFINAL RESULTS")
339 
 
 339 
 
340 
    lWinners = []
 340 
    lWinners = []
341 
    for winner in Universe.results.keys():
 341 
    for winner in Universe.results.keys():
342 
	if fParallel:
 342 
        if fParallel:
343 
	    lWinners.append("%f: %s" % (Universe.results[winner], winner))
 343 
            lWinners.append("%f: %s" % (Universe.results[winner], winner))
344 
	else:
 344 
        else:
345 
	    lWinners.append("%s" % winner)
 345 
            lWinners.append("%s" % winner)
346 
    lWinners.sort()
 346 
    lWinners.sort()
347 
    lWinners.reverse()
 347 
    lWinners.reverse()
348 
 
 348 
 
349 
    for winner in lWinners:
 349 
    for winner in lWinners:
350 
	trace(0, winner)
 350 
        trace(0, winner)
351 
 
 351 
 
352 
    return lWinners
 352 
    return lWinners