Subversion Repositories Remote Hare Voting

Rev

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

Rev 46 Rev 75
Line 1... Line 1...
1 
## Compute Hare Ballot
 1 
# Compute Hare Ballot
2 
##
 2 
#
3 
## Tim Korb (jtk@cs.purdue.edu), May 2007
 3 
# Tim Korb (jtk@cs.purdue.edu), May 2007
4 
##
 4 
#
5 
## A few definitions and notes...
 5 
# A few definitions and notes...
6 
##
 6 
#
7 
## tally: dictionary in which the keys are candidate names and the
 7 
# tally: dictionary in which the keys are candidate names and the
8 
## values are lists of ballots currently assigned to that candidate
 8 
# values are lists of ballots currently assigned to that candidate
9 
##
 9 
#
10 
## ballot: list of candidates in the order determined by the voter
 10 
# ballot: list of candidates in the order determined by the voter
11 
##
 11 
#
12 
## winners: list of candidates that have reached the quota of ballots
 12 
# winners: list of candidates that have reached the quota of ballots
13 
## or have remained in the running long enough to be declared a winner
 13 
# or have remained in the running long enough to be declared a winner
14 
##
 14 
#
15 
## losers: list of candidates that have been eliminated from the running
 15 
# losers: list of candidates that have been eliminated from the running
16 
##
 16 
#
17 
## Note that plurals are generally used to indicate lists of other
 17 
# Note that plurals are generally used to indicate lists of other
18 
## items, e.g., ballots is a list of ballot items.
 18 
# items, e.g., ballots is a list of ballot items.
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 
 
 25 
 
25 
import sys
 26 
import sys
26 
import math
27 
import math
- 
 
 28 
import copy
27 
import random
 29 
import random
28 
 
 30 
 
29 
fdOut = None
 31 
fdOut = None
30 
fTrace = 1
 - 
 
31 
randcalls = 0
 - 
 
32 
 
 32 
 
- 
 
 33 
traceLevel = 0	# generate trace output if trace >= trace parameter
- 
 
 34 
fParallel = 0	# track parallel universes instead of randomization if possible
- 
 
 35 
 
- 
 
 36 
class Universe:
- 
 
 37 
    id = 0                              # id of last created Universe
- 
 
 38 
    pendingUniverses = []
- 
 
 39 
    results = {}
- 
 
 40 
    dropped = 0
- 
 
 41 
 
- 
 
 42 
    def __reset(self):
- 
 
 43 
	Universe.id = 0
- 
 
 44 
 	Universe.pendingUniverses = []
- 
 
 45 
	Universe.results = {}
- 
 
 46 
	Universe.dropped = 0
- 
 
 47
- 
 
 48 
 
- 
 
 49 
    def __init__(self, p, nWinners, nBallots, quota):
- 
 
 50 
	if p == 1.0:
- 
 
 51 
	    self.__reset()
- 
 
 52 
        Universe.id += 1
- 
 
 53 
        self.id = Universe.id
- 
 
 54 
 
- 
 
 55 
        self.p = p
- 
 
 56 
	self.nWinners = nWinners
- 
 
 57 
        self.nBallots = nBallots
- 
 
 58 
        self.quota = quota
- 
 
 59 
 
- 
 
 60 
        self.winners = []
- 
 
 61 
        self.losers = []
- 
 
 62 
        self.tally = {}
- 
 
 63 
 
- 
 
 64 
	self.pendingItem = None
- 
 
 65 
	self.pendingType = None
- 
 
 66 
	self.pendingData = None
- 
 
 67 
 
- 
 
 68 
    def forkPendingWinners(self, lWin):
- 
 
 69 
	return self.__forkPendingList(lWin, "winner")
- 
 
 70 
 
- 
 
 71 
    def forkPendingLosers(self, lMin):
- 
 
 72 
	return self.__forkPendingList(lMin, "loser")
- 
 
 73 
 
- 
 
 74 
    def forkPendingRedist(self, lRedist, winner):
- 
 
 75 
	return self.__forkPendingList(lRedist, "redist", winner)
- 
 
 76 
 
- 
 
 77 
    def __forkPendingList(self, lItems, type, data=None):
- 
 
 78 
	global fParallel
- 
 
 79 
 
- 
 
 80 
        if len(lItems) == 1:
- 
 
 81 
	    return lItems[0]
- 
 
 82 
	if not fParallel:
- 
 
 83 
	    trace(1, "\tmaking random choice among %d alternatives" %
- 
 
 84 
		len(lItems))
- 
 
 85 
	    return random.choice(lItems)
- 
 
 86 
 
- 
 
 87 
	# Split into parallel universes unless too many with small probability
- 
 
 88 
	#
- 
 
 89 
	if Universe.id > 10000 and self.p/len(lItems) < 1.0/10000:
- 
 
 90 
	    trace(1, "\tpassing on %d universes (p = %f)" %
- 
 
 91 
		(len(lItems)-1, self.p/len(lItems)))
- 
 
 92 
	    trace(1, "\tmaking random choice among %d alternatives" %
- 
 
 93 
		len(lItems))
- 
 
 94 
	    Universe.dropped += len(lItems)-1
- 
 
 95 
	    return random.choice(lItems)
- 
 
 96 
 
- 
 
 97 
	self.p /= len(lItems)
- 
 
 98 
	trace(1, "\tcreating %d universes (p = %f)" % (len(lItems)-1, self.p))
- 
 
 99 
 
- 
 
 100 
	for item in lItems[1:]:
- 
 
 101 
	    u = Universe(self.p, self.nWinners, self.nBallots, self.quota)
- 
 
 102 
	    u.winners = self.winners[:]
- 
 
 103 
	    u.losers = self.losers[:]
- 
 
 104 
	    u.tally = copy.deepcopy(self.tally)
- 
 
 105 
	    u.pendingItem = item
- 
 
 106 
	    u.pendingType = type
- 
 
 107 
	    u.pendingData = data
- 
 
 108 
	    Universe.pendingUniverses.append(u)
- 
 
 109 
	return lItems[0]
- 
 
 110 
 
- 
 
 111 
def combinations(l, n):
- 
 
 112 
    if n == 0:
- 
 
 113 
	return [[]]
- 
 
 114 
    else:
- 
 
 115 
        lResult = []
- 
 
 116 
	for i in range(len(l)):
- 
 
 117 
	    for lsub in combinations(l[i+1:], n-1):
- 
 
 118 
		lResult.append([l[i]] + lsub)
- 
 
 119 
        return lResult
- 
 
 120 
 
33 
def trace(s):
 121 
def trace(t, s):
34 
    global fTrace, fdOut
 122 
    global traceLevel, fdOut
35 
    if fTrace: print >>fdOut, s
 123 
    if traceLevel >= t: print >>fdOut, s
36 
    return
 124 
    return
37 
 
 125 
 
38 
def findWinner(winners, losers, tally, quota, nWinners):
 - 
 
39 
    global randcalls
 126 
def findNextWinner(u):
40 
    cWin = quota       # number of votes for highest winner
 127 
    cWin = u.quota	# number of votes for highest winner
41 
    lWin = []          # list of candidates with highest votes
 128 
    lWin = []		# list of candidates with highest votes
42 
    for c in tally.keys():
 129 
    for c in u.tally.keys():
43 
        if c not in losers and c not in winners and len(tally[c]) >= cWin:
 130 
        if c not in u.losers and c not in u.winners and len(u.tally[c]) >= cWin:
44 
            if len(tally[c]) == cWin:
 131 
            if len(u.tally[c]) == cWin:
45 
                lWin.append(c)
 132 
                lWin.append(c)
46 
            else:
 133 
            else:
47 
                lWin = [c]
 134 
                lWin = [c]
48 
                cWin = len(tally[c])
 135 
                cWin = len(u.tally[c])
49 
    if len(lWin) == 1:
 - 
 
50 
        return lWin[0]
 - 
 
51 
    elif len(lWin) > 1:
 136 
    if len(lWin) > 0:
52 
        trace("\tselecting winning candidate randomly from %s" % lWin)
 - 
 
53 
        randcalls += 1
 - 
 
54 
        return random.choice(lWin)
 137 
        return u.forkPendingWinners(lWin)
55 
 
 138 
 
56 
    # Check to see if only enough candidates remain
 139 
    # Check to see if only enough candidates remain
57 
    ## TODO: sort by len(tally[c]) to choose larger winners first
 140 
    # TODO: sort by len(tally[c]) to choose larger winners first
58 
    ## randomize and count if some with equal votes
 141 
    # create multiple universes if some have equal votes
59 
    n = 0
 142 
    n = 0
60 
    last = ""
 143 
    last = ""
61 
    for c in tally.keys():
 144 
    for c in u.tally.keys():
62 
        if c not in winners and c not in losers:
 145 
        if c not in u.winners and c not in u.losers:
63 
            last = c
 146 
            last = c
64 
            n = n + 1
 147 
            n = n + 1
65 
    if nWinners - len(winners) >= n:
 148 
    if u.nWinners - len(u.winners) >= n:
66 
        trace("\tremaining winner(s) have fewer than quota (%d) ballots" %
 149 
        trace(1, "\tremaining winner(s) have fewer than quota (%d) ballots" %
67 
            quota)
 150 
            u.quota)
68 
        return last
 151 
        return last
69 
    return
 152 
    return
70 
 
 153 
 
71 
def redistributeWinner(winner, winners, losers, tally, quota):
 154 
def redistributeWinner(winner, u):
72 
    global randcalls
 - 
 
73 
    excess = len(tally[winner]) - quota
 155 
    excess = len(u.tally[winner]) - u.quota
74 
    if excess <= 0:
 156 
    if excess <= 0:
75 
        trace("\tno excess ballots to redistribute")
 157 
        trace(1, "\tno excess ballots to redistribute")
76 
    else:
 158 
    else:
77 
	lEffective = gatherEffectiveBallots(winner, winners, losers, tally)
 159 
        lEffective = gatherEffectiveBallots(winner, u)
78 
        nRedistribute = min(excess, len(lEffective))
 160 
        nRedist = min(excess, len(lEffective))
79 
        trace("\tredistributing %d effective of %d excess ballot(s) at random from %s" %
 161 
	trace(1, "\tredistributing %d effective ballots, %d at a time" %
80 
              (nRedistribute, excess, winner))
 162 
	    (len(lEffective), nRedist))
81 
        for ballot in random.sample(lEffective, nRedistribute):
 163 
	for ballot in u.forkPendingRedist(combinations(lEffective, nRedist), winner):
82 
            randcalls += 1
 - 
 
83 
            trace("\trandom choice = %s" % ballot)
 - 
 
84 
            tally[winner].remove(ballot)
 164 
            u.tally[winner].remove(ballot)
85 
            redistributeBallot(ballot, winners, losers, tally)
 165 
            redistributeBallot(ballot, u)
86 
            nRedistribute -= 1
 - 
 
87 
    traceTally(quota, tally)
 166 
    traceTally(1, u)
88 
 
 167 
 
89 
def gatherEffectiveBallots(winner, winners, losers, tally):
 168 
def gatherEffectiveBallots(winner, u):
90 
    lEffective = []
 169 
    lEffective = []
91 
    for ballot in tally[winner]:
 170 
    for ballot in u.tally[winner]:
92 
        for candidateTo in ballot:
 171 
        for candidateTo in ballot:
93 
           if candidateTo not in winners and candidateTo not in losers:
 172 
           if candidateTo not in u.winners and candidateTo not in u.losers:
94 
                lEffective.append(ballot)
 173 
                lEffective.append(ballot)
95 
                break
 174 
                break
96 
    return lEffective
 175 
    return lEffective
97 
 
 176 
 
98 
def redistributeBallot(ballot, winners, losers, tally):
 177 
def redistributeBallot(ballot, u):
99 
    for candidateTo in ballot:
 178 
    for candidateTo in ballot:
100 
        if candidateTo not in winners and candidateTo not in losers:
 179 
        if candidateTo not in u.winners and candidateTo not in u.losers:
101 
            trace("\tto %s: %s" % (candidateTo, ballot))
 180 
            trace(1, "\tto %s: %s" % (candidateTo, ballot))
102 
            if not tally.has_key(candidateTo): tally[candidateTo] = []
 181 
            if not u.tally.has_key(candidateTo): u.tally[candidateTo] = []
103 
            tally[candidateTo].append(ballot)
 182 
            u.tally[candidateTo].append(ballot)
104 
            ballot = ""
 183 
            ballot = ""
105 
            break
 184 
            break
106 
    if ballot:
 185 
    if ballot:
107 
        trace("\tineffective ballot dropped: %s" % ballot)
 186 
        trace(1, "\tineffective ballot dropped: %s" % ballot)
108 
 
 187 
 
109 
def findLoser(losers, winners, tally):
 188 
def findNextLoser(u):
110 
    global randcalls
 - 
 
111 
    cMin = sys.maxint  # least number of votes for candidate loser
 189 
    cMin = sys.maxint  # least number of votes for candidate loser
112 
    lMin = []          # list of candidates with least votes
 190 
    lMin = []          # list of candidates with least votes
113 
    for c in tally.keys():
 191 
    for c in u.tally.keys():
114 
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
 192 
        if c not in u.losers and c not in u.winners and len(u.tally[c]) <= cMin:
115 
            if len(tally[c]) == cMin:
 193 
            if len(u.tally[c]) == cMin:
116 
                lMin.append(c)
 194 
                lMin.append(c)
117 
            else:
 195 
            else:
118 
                lMin = [c]
 196 
                lMin = [c]
119 
                cMin = len(tally[c])
 197 
                cMin = len(u.tally[c])
120 
    if len(lMin) == 0:
 198 
    if len(lMin) == 0:
121 
        return None
 199 
        return None
122 
    elif len(lMin) == 1:
 - 
 
123 
        return lMin[0]
 - 
 
124 
    else:
 200 
    else:
125 
        trace("\teliminating low candidate randomly from %s" % lMin)
 - 
 
126 
        randcalls += 1
 - 
 
127 
        return random.choice(lMin)
 201 
        return u.forkPendingLosers(lMin)
128 
 
 202 
 
129 
def redistributeLoser(loser, losers, winners, tally, quota):
 203 
def redistributeLoser(loser, u):
130 
    excess = len(tally[loser])
 204 
    excess = len(u.tally[loser])
131 
    if excess <= 0:
 205 
    if excess <= 0:
132 
        trace("\tno ballots to redistribute")
 206 
        trace(1, "\tno ballots to redistribute")
133 
    else:
 207 
    else:
134 
        trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
 208 
        trace(1, "\tredistributing %d ballot(s) from %s" % (excess, loser))
135 
        while len(tally[loser]) > 0:
 209 
        while len(u.tally[loser]) > 0:
136 
            ballot = tally[loser][0]
 210 
            ballot = u.tally[loser][0]
137 
            tally[loser] = tally[loser][1:]
 211 
            u.tally[loser] = u.tally[loser][1:]
138 
            redistributeBallot(ballot, winners, losers, tally)
 212 
            redistributeBallot(ballot, u)
139 
    traceTally(quota, tally)
 213 
    traceTally(1, u)
140 
    return
 214 
    return
141 
 
 215 
 
142 
def traceTally(quota, tally):
 216 
def traceTally(t, u):
143 
    global fTrace
 217 
    global traceLevel
144 
    if not fTrace: return
 218 
    if traceLevel < t: return
145 
    trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % quota)
 219 
    trace(t, "\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % u.quota)
146 
    for candidate in tally.keys():
 220 
    for candidate in u.tally.keys():
147 
        trace("\t%s:" % candidate)
 221 
        trace(t, "\t%s:" % candidate)
148 
        for ballot in tally[candidate]:
 222 
        for ballot in u.tally[candidate]:
149 
            trace("\t\t%s" % ballot)
 223 
            trace(t, "\t\t%s" % ballot)
150 
    return
 224 
    return
151 
 
 225 
 
152 
# The basic Single Transferable Vote algorithm with Hare quota
 226 
# The basic Single Transferable Vote algorithm with Hare quota
153 
#
 227 
#
154 
# while winners < nWinners:
 228 
# while winners < nWinners:
Line 157... Line 231...
157 
#   else:
 231 
#   else:
158 
#       eliminate lowest ranking candidate
 232 
#       eliminate lowest ranking candidate
159 
#       redistribute wasted votes to next priority candidate
 233 
#       redistribute wasted votes to next priority candidate
160 
#
 234 
#
161 
def dotally(nWinners, ballots):
 235 
def dotally(nWinners, ballots):
162 
    global randcalls
 236 
    global fParallel
163 
    randcalls = 0
 - 
 
- 
 
 237 
 
164 
    nBallots = len(ballots)
 238 
    nBallots=len(ballots)
165 
    quota = int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
 239 
    quota=int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
- 
 
 240 
 
- 
 
 241 
    u = Universe(1.0, nWinners, nBallots, quota)
166 
 
 242 
 
167 
    trace("INPUT SUMMARY AND SINGLE RUN TRACE")
 243 
    trace(0, "INPUT SUMMARY")
168 
    trace("\t%d ballots" % nBallots)
 244 
    trace(0, "\t%d ballots" % u.nBallots)
169 
    trace("\tChoosing %s winners" % nWinners)
 245 
    trace(0, "\tChoosing %s winners" % u.nWinners)
170 
    trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
 246 
    trace(0, "\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
171 
          (nBallots, nWinners, quota))
 247 
          (u.nBallots, u.nWinners, u.quota))
172 
 
 248 
 
173 
    # Create initial tally and statistics
 249 
    # Create initial tally and statistics
174 
    #
 250 
    #
175 
    tally = {}
 - 
 
176 
    for ballot in ballots:
 251 
    for ballot in ballots:
177 
        candidate = ballot[0]
 252 
        candidate = ballot[0]
178 
        if not tally.has_key(candidate):
 253 
        if not u.tally.has_key(candidate):
179 
            tally[candidate] = []
 254 
            u.tally[candidate] = []
180 
        tally[candidate].append(ballot)
 255 
        u.tally[candidate].append(ballot)
181 
 
 256 
 
182 
    total1st = {}
 257 
    total1st = {}
183 
    total2nd = {}
 258 
    total2nd = {}
184 
    totalMrk = {}
 259 
    totalMrk = {}
185 
 
 260 
 
Line 194... Line 269...
194 
        if len(ballot) > 1:
 269 
        if len(ballot) > 1:
195 
            total2nd[ballot[1]] += 1
 270 
            total2nd[ballot[1]] += 1
196 
        for c in ballot:
 271 
        for c in ballot:
197 
            totalMrk[c] += 1
 272 
            totalMrk[c] += 1
198 
 
 273 
 
199 
    trace("\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
 274 
    trace(0, "\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
200 
    candidates = totalMrk.keys()
 275 
    candidates = totalMrk.keys()
201 
    candidates.sort()
 276 
    candidates.sort()
202 
    for c in candidates:
 277 
    for c in candidates:
- 
 
 278 
        trace(0, "\t%-16s%3d\t%3d\t%4d" %
203 
        trace("\t%-16s%3d\t%3d\t%4d" % (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
 279 
	    (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
204 
    traceTally(quota, tally)
 280 
    traceTally(0, u)
205
281 
 
206 
    winners = []
 282 
    Universe.pendingUniverses.append(u)
- 
 
 283 
 
207 
    losers = []
 284 
    while len(Universe.pendingUniverses) > 0:
- 
 
 285 
    	u = Universe.pendingUniverses.pop()
- 
 
 286 
	trace(1, "POPPED UNIVERSE %d (p = %f, %d pending):" %
- 
 
 287 
	    (u.id, u.p, len(Universe.pendingUniverses)))
208 
 
 288 
 
- 
 
 289 
	if u.pendingType == "redist":
- 
 
 290 
	    trace(1, "\tredistributing %d ballots" % len(u.pendingItem))
- 
 
 291 
	    winner = u.pendingData
209 
    while len(winners) < nWinners:
 292 
	    assert(winner in u.winners)
- 
 
 293 
	    for ballot in u.pendingItem:
- 
 
 294 
                u.tally[winner].remove(ballot)
210 
        winner = findWinner(winners, losers, tally, quota, nWinners)
 295 
                redistributeBallot(ballot, u)
211 
        if winner:
 296 
        elif u.pendingType == "winner":
- 
 
 297 
	    trace(1, "\tfinishing pending winner %s" % u.pendingItem)
- 
 
 298 
	    winner = u.pendingItem
- 
 
 299 
	    assert(winner not in u.winners)
212 
            winners.append(winner)
 300 
            u.winners.append(winner)
213 
            trace("\nSELECTION #%d: %s" % (len(winners), winner))
 301 
            trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
214 
            redistributeWinner(winner, winners, losers, tally, quota)
 302 
            redistributeWinner(winner, u)
- 
 
 303 
	elif u.pendingType == "loser":
- 
 
 304 
	    trace(1, "\tfinishing pending loser %s" % u.pendingItem)
- 
 
 305 
	    loser = u.pendingItem
- 
 
 306 
            u.losers.append(loser)
- 
 
 307 
            trace(1, "\nELIMINATED: %s" % loser)
- 
 
 308 
            redistributeLoser(loser, u)
- 
 
 309 
 
215 
        else:
 310 
        u.pendingType = None
- 
 
 311 
 
- 
 
 312 
        while len(u.winners) < u.nWinners:
216 
            loser = findLoser(losers, winners, tally)
 313 
            winner = findNextWinner(u)
217 
            if loser:
 314 
            if winner:
218 
                losers.append(loser)
 315 
                u.winners.append(winner)
219 
                trace("\nELIMINATED: %s" % loser)
 316 
                trace(1, "\nSELECTION #%d: %s" % (len(u.winners), winner))
220 
                redistributeLoser(loser, losers, winners, tally, quota)
 317 
                redistributeWinner(winner, u)
221 
            else:
 318 
            else:
- 
 
 319 
	        loser = findNextLoser(u)
- 
 
 320 
                if loser:
- 
 
 321 
                    u.losers.append(loser)
- 
 
 322 
                    trace(1, "\nELIMINATED: %s" % loser)
- 
 
 323 
                    redistributeLoser(loser, u)
- 
 
 324 
                else:
222 
                trace("Not enough chosen candidates to fill all positions")
 325 
                    trace(1, "Not enough chosen candidates to fill all positions")
223 
                break
 326 
                    break
- 
 
 327 
 
- 
 
 328 
	winners = str(u.winners)
- 
 
 329 
	if fParallel:
224 
    trace("\nNumber of random choices made: %d" % randcalls)
 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
- 
 
 332 
	Universe.results[winners] += u.p
- 
 
 333 
 
- 
 
 334 
    if fParallel:
- 
 
 335 
	trace(0, "\nTracked %d alternative decisions (skipped %d with low probability)" %
- 
 
 336 
	    (Universe.id, Universe.dropped))
- 
 
 337 
 
- 
 
 338 
    trace(0, "\nFINAL RESULTS")
- 
 
 339 
 
- 
 
 340 
    lWinners = []
- 
 
 341 
    for winner in Universe.results.keys():
- 
 
 342 
	if fParallel:
- 
 
 343 
	    lWinners.append("%f: %s" % (Universe.results[winner], winner))
- 
 
 344 
	else:
- 
 
 345 
	    lWinners.append("%s" % winner)
- 
 
 346 
    lWinners.sort()
- 
 
 347 
    lWinners.reverse()
225 
 
 348 
 
- 
 
 349 
    for winner in lWinners:
226 
    return winners
 350 
	trace(0, winner)
227 
 
 351 
 
- 
 
 352 
    return lWinners