WebSVN – Remote Hare Voting – Diff – /branches/multiverse/tally.py

 fdOut = None
 fTrace = 1
 randcalls = 0
 class Universe:
-    id = 0                              # id of last create Universe
+    id = 0                              # id of last created Universe
+    pendingUniverses = []
+    completedUniverses = []
     def __init__(self, p, nWinners, nBallots, quota):
         Universe.id += 1
         self.id = Universe.id
         self.p = p
         self.quota = quota
         self.winners = []
         self.losers = []
         self.tally = {}
-    def getP(self):
+    def forkPendingWinners(self, lWin):
+	return self.__forkPendingList(lWin, "winner")
-        print "instance p =", self.p
+    def forkPendingLosers(self, lMin):
+	return self.__forkPendingList(lMin, "loser")
+    def forkPendingRedist(self, lRedist):
+	return self.__forkPendingList(lRedist, "redist")
+    def __forkPendingList(self, lItems, pendingType):
+	self.p /= len(lItems)
+	for item in lItems[1:]:
+	    u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
-        print "class p =", Universe.p
+	    u.winners = self.winners[:]
+	    u.losers = self.losers[:]
+	    u.tally = self.tally.copy()
+	    u.pending = item
+	    u.pendingType = pendingType
+	    Universe.pendingUniverses.append(u)
+	return lItems[0]
+def combinations(l, n):
+    assert(n >= 0)
+    if n == 0:
+	yield []
+    else:
+	for i in range(len(l)):
+	    for lsub in combinations(l[i+1:], n-1):
+		yield [l[i]] + lsub
 def trace(s):
     global fTrace, fdOut
     if fTrace: print >>fdOut, s
     return
-def findWinner(winners, losers, tally, quota, nWinners):
+def findNextWinner(u):
     global randcalls
-    cWin = quota        # number of votes for highest winner
+    cWin = u.quota	# number of votes for highest winner
-    lWin = []           # list of candidates with highest votes
+    lWin = []		# list of candidates with highest votes
-    for c in tally.keys():
+    for c in u.tally.keys():
-        if c not in losers and c not in winners and len(tally[c]) >= cWin:
+        if c not in u.losers and c not in u.winners and len(u.tally[c]) >= cWin:
-            if len(tally[c]) == cWin:
+            if len(u.tally[c]) == cWin:
                 lWin.append(c)
             else:
                 lWin = [c]
-                cWin = len(tally[c])
+                cWin = len(u.tally[c])
-    if len(lWin) == 1:
-        return lWin[0]
-    elif len(lWin) > 1:
+    if len(lWin) > 0:
-        trace("\tselecting winning candidate randomly from %s" % lWin)
-        randcalls += 1
-        return random.choice(lWin)
+        return u.forkPendingWinners(lWin)
     # Check to see if only enough candidates remain
     ## TODO: sort by len(tally[c]) to choose larger winners first
     ## randomize and count if some with equal votes
     n = 0
     last = ""
-    for c in tally.keys():
+    for c in u.tally.keys():
-        if c not in winners and c not in losers:
+        if c not in u.winners and c not in u.losers:
             last = c
             n = n + 1
-    if nWinners - len(winners) >= n:
+    if u.nWinners - len(u.winners) >= n:
         trace("\tremaining winner(s) have fewer than quota (%d) ballots" %
-            quota)
+            u.quota)
         return last
     return
-def redistributeWinner(winner, winners, losers, tally, quota):
+def redistributeWinner(winner, u):
     global randcalls
-    excess = len(tally[winner]) - quota
+    excess = len(u.tally[winner]) - u.quota
     if excess <= 0:
         trace("\tno excess ballots to redistribute")
     else:
-        lEffective = gatherEffectiveBallots(winner, winners, losers, tally)
+        lEffective = gatherEffectiveBallots(winner, u)
         nRedistribute = min(excess, len(lEffective))
         trace("\tredistributing %d effective of %d excess ballot(s) at random from %s" %
               (nRedistribute, excess, winner))
+## LEFT OFF HERE...
+## 	Need to create (len(lEffective) choose nRedistribute)-1 universes.
+##  	One solution is to set self.nRedistribute, then forkPendingRedist the lEffective ballots.
+## 	Must wind up with nRedistribute ballots redistributed in current universe.
+## 	u.forkPendingRedist(lEffective)
         for ballot in random.sample(lEffective, nRedistribute):
             randcalls += 1
             trace("\trandom choice = %s" % ballot)
-            tally[winner].remove(ballot)
+            u.tally[winner].remove(ballot)
-            redistributeBallot(ballot, winners, losers, tally)
+            redistributeBallot(ballot, u)
             nRedistribute -= 1
-    traceTally(quota, tally)
+    traceTally(u)
-def gatherEffectiveBallots(winner, winners, losers, tally):
+def gatherEffectiveBallots(winner, u):
     lEffective = []
-    for ballot in tally[winner]:
+    for ballot in u.tally[winner]:
         for candidateTo in ballot:
-           if candidateTo not in winners and candidateTo not in losers:
+           if candidateTo not in u.winners and candidateTo not in u.losers:
                 lEffective.append(ballot)
                 break
     return lEffective
-def redistributeBallot(ballot, winners, losers, tally):
+def redistributeBallot(ballot, u):
     for candidateTo in ballot:
-        if candidateTo not in winners and candidateTo not in losers:
+        if candidateTo not in u.winners and candidateTo not in u.losers:
             trace("\tto %s: %s" % (candidateTo, ballot))
-            if not tally.has_key(candidateTo): tally[candidateTo] = []
+            if not u.tally.has_key(candidateTo): u.tally[candidateTo] = []
-            tally[candidateTo].append(ballot)
+            u.tally[candidateTo].append(ballot)
             ballot = ""
             break
     if ballot:
         trace("\tineffective ballot dropped: %s" % ballot)
-def findLoser(losers, winners, tally):
+def findNextLoser(u):
     global randcalls
     cMin = sys.maxint  # least number of votes for candidate loser
     lMin = []          # list of candidates with least votes
-    for c in tally.keys():
+    for c in u.tally.keys():
-        if c not in losers and c not in winners and len(tally[c]) <= cMin:
+        if c not in u.losers and c not in u.winners and len(u.tally[c]) <= cMin:
-            if len(tally[c]) == cMin:
+            if len(u.tally[c]) == cMin:
                 lMin.append(c)
             else:
                 lMin = [c]
-                cMin = len(tally[c])
+                cMin = len(u.tally[c])
     if len(lMin) == 0:
         return None
-    elif len(lMin) == 1:
-        return lMin[0]
     else:
-        trace("\teliminating low candidate randomly from %s" % lMin)
-        randcalls += 1
-        return random.choice(lMin)
+        return u.forkPendingLosers(lMin)
-def redistributeLoser(loser, losers, winners, tally, quota):
+def redistributeLoser(loser, u):
-    excess = len(tally[loser])
+    excess = len(u.tally[loser])
     if excess <= 0:
         trace("\tno ballots to redistribute")
     else:
         trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
-        while len(tally[loser]) > 0:
+        while len(u.tally[loser]) > 0:
-            ballot = tally[loser][0]
+            ballot = u.tally[loser][0]
-            tally[loser] = tally[loser][1:]
+            u.tally[loser] = u.tally[loser][1:]
-            redistributeBallot(ballot, winners, losers, tally)
+            redistributeBallot(ballot, u)
-    traceTally(quota, tally)
+    traceTally(u)
     return
-def traceTally(quota, tally):
+def traceTally(u):
     global fTrace
     if not fTrace: return
-    trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % quota)
+    trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % u.quota)
-    for candidate in tally.keys():
+    for candidate in u.tally.keys():
         trace("\t%s:" % candidate)
-        for ballot in tally[candidate]:
+        for ballot in u.tally[candidate]:
             trace("\t\t%s" % ballot)
     return
 # The basic Single Transferable Vote algorithm with Hare quota
+#
     randcalls = 0
     nBallots=len(ballots)
     quota=int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
-    universe = Universe(1.0, nWinners, nBallots, quota)
+    u = Universe(1.0, nWinners, nBallots, quota)
     trace("INPUT SUMMARY AND RUN TRACE")
-    trace("\t%d ballots" % universe.nBallots)
+    trace("\t%d ballots" % u.nBallots)
-    trace("\tChoosing %s winners" % universe.nWinners)
+    trace("\tChoosing %s winners" % u.nWinners)
     trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
-          (universe.nBallots, universe.nWinners, universe.quota))
+          (u.nBallots, u.nWinners, u.quota))
     # Create initial tally and statistics
+    #
     for ballot in ballots:
         candidate = ballot[0]
-        if not universe.tally.has_key(candidate):
+        if not u.tally.has_key(candidate):
-            universe.tally[candidate] = []
+            u.tally[candidate] = []
-        universe.tally[candidate].append(ballot)
+        u.tally[candidate].append(ballot)
     total1st = {}
     total2nd = {}
     totalMrk = {}
     trace("\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
     candidates = totalMrk.keys()
     candidates.sort()
     for c in candidates:
         trace("\t%-16s%3d\t%3d\t%4d" % (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
-    traceTally(universe.quota, universe.tally)
+    traceTally(u)
-    continueTally(universe)
+    continueTally(u)
-    return universe.winners
+    return u.winners
-def continueTally(universe):
+def continueTally(u):
-    while len(universe.winners) < universe.nWinners:
+    while len(u.winners) < u.nWinners:
-        winner = findWinner(universe.winners, universe.losers, universe.tally, universe.quota, universe.nWinners)
+        winner = findNextWinner(u)
         if winner:
-            universe.winners.append(winner)
+            u.winners.append(winner)
-            trace("\nSELECTION #%d: %s" % (len(universe.winners), winner))
+            trace("\nSELECTION #%d: %s" % (len(u.winners), winner))
-            redistributeWinner(winner, universe.winners, universe.losers, universe.tally, universe.quota)
+            redistributeWinner(winner, u)
         else:
-            loser = findLoser(universe.losers, universe.winners, universe.tally)
+            loser = findNextLoser(u)
             if loser:
-                universe.losers.append(loser)
+                u.losers.append(loser)
                 trace("\nELIMINATED: %s" % loser)
-                redistributeLoser(loser, universe.losers, universe.winners, universe.tally, universe.quota)
+                redistributeLoser(loser, u)
             else:
                 trace("Not enough chosen candidates to fill all positions")
                 break
     trace("\nNumber of random choices made: %d" % randcalls)

Subversion Repositories Remote Hare Voting

(root)/branches/multiverse/tally.py – Rev 55 → 57