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

 ##
 ## To download the complete source distribution, use Subversion:
 ##
 ##      % svn co http://www.bikmort.com/hare
 ##
-## $Id: tally.py 62 2007-09-24 13:57:27Z jtkorb $
+## $Id: tally.py 63 2007-09-25 03:00:26Z jtkorb $
 import sys
 import math
 import copy
 import random
 fdOut = None
-fTrace = 1
+traceLevel = 0	# generate trace output if trace >= trace parameter
+fParallel = 0	# track parallel universes instead of randomization if possible
 class Universe:
     id = 0                              # id of last created Universe
     pendingUniverses = []
     results = {}
     def forkPendingRedist(self, lRedist, winner):
 	return self.__forkPendingList(lRedist, "redist", winner)
     def __forkPendingList(self, lItems, type, data=None):
+	global fParallel
         if len(lItems) == 1:
 	    return lItems[0]
+	if not fParallel:
+	    trace(1, "\tmaking random choice among %d alternatives" %
+		len(lItems))
+	    return random.choice(lItems)
+	# Split into parallel universes unless too many with small probability
+	#
-	if self.p/len(lItems) < 1.0/1000000:
+	if Universe.id > 10000 and self.p/len(lItems) < 1.0/10000:
-	    trace("\tpassing on %d universes (p = %f)" % (len(lItems)-1, self.p/len(lItems)))
+	    trace(1, "\tpassing on %d universes (p = %f)" %
+		(len(lItems)-1, self.p/len(lItems)))
+	    trace(1, "\tmaking random choice among %d alternatives" %
+		len(lItems))
 	    Universe.dropped += len(lItems)-1
 	    return random.choice(lItems)
 	self.p /= len(lItems)
-	trace("\tcreating %d universes (p = %f)" % (len(lItems)-1, self.p))
+	trace(1, "\tcreating %d universes (p = %f)" % (len(lItems)-1, self.p))
 	for item in lItems[1:]:
 	    u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
 	    u.winners = self.winners[:]
 	    u.losers = self.losers[:]
 	    u.tally = copy.deepcopy(self.tally)
 	for i in range(len(l)):
 	    for lsub in combinations(l[i+1:], n-1):
 		lResult.append([l[i]] + lsub)
         return lResult
-def trace(s):
+def trace(t, s):
-    global fTrace, fdOut
+    global traceLevel, fdOut
-    if fTrace: print >>fdOut, s
+    if traceLevel >= t: print >>fdOut, s
     return
 def findNextWinner(u):
     cWin = u.quota	# number of votes for highest winner
     lWin = []		# list of candidates with highest votes
     for c in u.tally.keys():
         if c not in u.winners and c not in u.losers:
             last = c
             n = n + 1
     if u.nWinners - len(u.winners) >= n:
-        trace("\tremaining winner(s) have fewer than quota (%d) ballots" %
+        trace(1, "\tremaining winner(s) have fewer than quota (%d) ballots" %
             u.quota)
         return last
     return
 def redistributeWinner(winner, u):
     excess = len(u.tally[winner]) - u.quota
     if excess <= 0:
-        trace("\tno excess ballots to redistribute")
+        trace(1, "\tno excess ballots to redistribute")
     else:
         lEffective = gatherEffectiveBallots(winner, u)
         nRedist = min(excess, len(lEffective))
-	trace("\tredistributing %d effective ballots, %d at a time" % (len(lEffective), nRedist))
+	trace(1, "\tredistributing %d effective ballots, %d at a time" %
+	    (len(lEffective), nRedist))
 	for ballot in u.forkPendingRedist(combinations(lEffective, nRedist), winner):
             u.tally[winner].remove(ballot)
             redistributeBallot(ballot, u)
-    traceTally(u)
+    traceTally(1, u)
 def gatherEffectiveBallots(winner, u):
     lEffective = []
     for ballot in u.tally[winner]:
         for candidateTo in ballot:
     return lEffective
 def redistributeBallot(ballot, u):
     for candidateTo in ballot:
         if candidateTo not in u.winners and candidateTo not in u.losers:
-            trace("\tto %s: %s" % (candidateTo, ballot))
+            trace(1, "\tto %s: %s" % (candidateTo, ballot))
             if not u.tally.has_key(candidateTo): u.tally[candidateTo] = []
             u.tally[candidateTo].append(ballot)
             ballot = ""
             break
     if ballot:
-        trace("\tineffective ballot dropped: %s" % ballot)
+        trace(1, "\tineffective ballot dropped: %s" % ballot)
 def findNextLoser(u):
     cMin = sys.maxint  # least number of votes for candidate loser
     lMin = []          # list of candidates with least votes
     for c in u.tally.keys():
         return u.forkPendingLosers(lMin)
 def redistributeLoser(loser, u):
     excess = len(u.tally[loser])
     if excess <= 0:
-        trace("\tno ballots to redistribute")
+        trace(1, "\tno ballots to redistribute")
     else:
-        trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
+        trace(1, "\tredistributing %d ballot(s) from %s" % (excess, loser))
         while len(u.tally[loser]) > 0:
             ballot = u.tally[loser][0]
             u.tally[loser] = u.tally[loser][1:]
             redistributeBallot(ballot, u)
-    traceTally(u)
+    traceTally(1, u)
     return
-def traceTally(u):
+def traceTally(t, u):
-    global fTrace
+    global traceLevel
-    if not fTrace: return
+    if traceLevel < t: return
-    trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % u.quota)
+    trace(t, "\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % u.quota)
     for candidate in u.tally.keys():
-        trace("\t%s:" % candidate)
+        trace(t, "\t%s:" % candidate)
         for ballot in u.tally[candidate]:
-            trace("\t\t%s" % ballot)
+            trace(t, "\t\t%s" % ballot)
     return
 # The basic Single Transferable Vote algorithm with Hare quota
+#
 # while winners < nWinners:
 #   else:
 #       eliminate lowest ranking candidate
 #       redistribute wasted votes to next priority candidate
+#
 def dotally(nWinners, ballots):
+    global fParallel
     nBallots=len(ballots)
     quota=int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
     u = Universe(1.0, nWinners, nBallots, quota)
-    trace("INPUT SUMMARY AND RUN TRACE")
+    trace(0, "INPUT SUMMARY")
-    trace("\t%d ballots" % u.nBallots)
+    trace(0, "\t%d ballots" % u.nBallots)
-    trace("\tChoosing %s winners" % u.nWinners)
+    trace(0, "\tChoosing %s winners" % u.nWinners)
-    trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
+    trace(0, "\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
           (u.nBallots, u.nWinners, u.quota))
     # Create initial tally and statistics
+    #
     for ballot in ballots:
         if len(ballot) > 1:
             total2nd[ballot[1]] += 1
         for c in ballot:
             totalMrk[c] += 1
-    trace("\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
+    trace(0, "\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
     candidates = totalMrk.keys()
     candidates.sort()
     for c in candidates:
+        trace(0, "\t%-16s%3d\t%3d\t%4d" %
-        trace("\t%-16s%3d\t%3d\t%4d" % (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
+	    (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
-    traceTally(u)
+    traceTally(0, u)
     Universe.pendingUniverses.append(u)
     while len(Universe.pendingUniverses) > 0:
     	u = Universe.pendingUniverses.pop()
-	trace("POPPED UNIVERSE %d (p = %f, %d pending):" %
+	trace(1, "POPPED UNIVERSE %d (p = %f, %d pending):" %
 	    (u.id, u.p, len(Universe.pendingUniverses)))
 	if u.pendingType == "redist":
-	    trace("\tredistributing %d ballots" % len(u.pendingItem))
+	    trace(1, "\tredistributing %d ballots" % len(u.pendingItem))
 	    winner = u.pendingData
 	    assert(winner in u.winners)
 	    for ballot in u.pendingItem:
                 u.tally[winner].remove(ballot)
                 redistributeBallot(ballot, u)
         elif u.pendingType == "winner":
-	    trace("\tfinishing pending winner %s" % u.pendingItem)
+	    trace(1, "\tfinishing pending winner %s" % u.pendingItem)
 	    winner = u.pendingItem
 	    assert(winner not in u.winners)
             u.winners.append(winner)
-            trace("\nSELECTION #%d: %s" % (len(u.winners), winner))
+            trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
             redistributeWinner(winner, u)
 	elif u.pendingType == "loser":
-	    trace("\tfinishing pending loser %s" % u.pendingItem)
+	    trace(1, "\tfinishing pending loser %s" % u.pendingItem)
 	    loser = u.pendingItem
             u.losers.append(loser)
-            trace("\nELIMINATED: %s" % loser)
+            trace(1, "\nELIMINATED: %s" % loser)
             redistributeLoser(loser, u)
         u.pendingType = None
         while len(u.winners) < u.nWinners:
             winner = findNextWinner(u)
             if winner:
                 u.winners.append(winner)
-                trace("\nSELECTION #%d: %s" % (len(u.winners), winner))
+                trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
                 redistributeWinner(winner, u)
             else:
 	        loser = findNextLoser(u)
                 if loser:
                     u.losers.append(loser)
-                    trace("\nELIMINATED: %s" % loser)
+                    trace(1, "\nELIMINATED: %s" % loser)
                     redistributeLoser(loser, u)
                 else:
-                    trace("Not enough chosen candidates to fill all positions")
+                    trace(1, "Not enough chosen candidates to fill all positions")
                     break
 	winners = str(u.winners)
-	trace("RESULTS FOR UNIVERSE %d (p = %f): %s" % (u.id, u.p, winners))
+	trace(1, "RESULTS FOR UNIVERSE %d (p = %f): %s" % (u.id, u.p, winners))
 	if winners not in Universe.results: Universe.results[winners] = 0.0
 	Universe.results[winners] += u.p
+    if fParallel:
-    trace("\nUsed %d parallel universes (skipped %d with low probability)" %
+	trace(0, "\nUsed %d parallel universes (skipped %d low probability)" %
-	(Universe.id, Universe.dropped))
+	    (Universe.id, Universe.dropped))
+    trace(0, "\nFINAL RESULTS")
     lWinners = []
     for winner in Universe.results.keys():
 	lWinners.append("%f: %s" % (Universe.results[winner], winner))
     lWinners.sort()
     lWinners.reverse()
+    for winner in lWinners:
+	trace(0, winner)
     return lWinners

Subversion Repositories Remote Hare Voting

(root)/branches/multiverse/tally.py – Rev 62 → 63