Subversion Repositories Local Hare Voting

Rev

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

Rev 15 Rev 21
Line 46... Line 46...
46 
    return
 46 
    return
47 
 
 47 
 
48 
def redistributeWinner(winner, winners, losers, tally, quota):
 48 
def redistributeWinner(winner, winners, losers, tally, quota):
49 
    excess = len(tally[winner]) - quota
 49 
    excess = len(tally[winner]) - quota
50 
    if excess <= 0:
 50 
    if excess <= 0:
51 
	trace("\tno excess ballots to redistribute")
 51 
        trace("\tno excess ballots to redistribute")
52 
    else:
 52 
    else:
53 
	trace("\tredistributing %d excess ballot(s) at random from %s" %
 53 
        trace("\tredistributing %d excess ballot(s) at random from %s" %
54 
	      (excess, winner))
 54 
              (excess, winner))
55 
	while len(tally[winner]) > quota:
 55 
        while len(tally[winner]) > quota:
56 
	    i = int(random.uniform(0, len(tally[winner])))
 56 
            i = int(random.uniform(0, len(tally[winner])))
57 
	    trace("\trandom choice = ballot %d" % (i+1))
 57 
            trace("\trandom choice = ballot %d" % (i+1))
58 
	    ballot = tally[winner][i]
 58 
            ballot = tally[winner][i]
59 
	    tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
 59 
            tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
60 
	    redistributeBallot(ballot, winner, winners, losers, tally)
 60 
            redistributeBallot(ballot, winner, winners, losers, tally)
61 
    traceTally(quota, tally)
 61 
    traceTally(quota, tally)
62 
 
 62 
 
63 
def redistributeBallot(ballot, candidateFrom, winners, losers, tally):
 63 
def redistributeBallot(ballot, candidateFrom, winners, losers, tally):
64 
    for candidateTo in ballot:
 64 
    for candidateTo in ballot:
65 
	if candidateTo not in winners and candidateTo not in losers:
 65 
        if candidateTo not in winners and candidateTo not in losers:
66 
	    trace("\tto %s: %s" % (candidateTo, ballot))
 66 
            trace("\tto %s: %s" % (candidateTo, ballot))
67 
	    if not tally.has_key(candidateTo): tally[candidateTo] = []
 67 
            if not tally.has_key(candidateTo): tally[candidateTo] = []
68 
	    tally[candidateTo].append(ballot)
 68 
            tally[candidateTo].append(ballot)
69 
	    ballot = ""
 69 
            ballot = ""
70 
	    break
 70 
            break
71 
    if ballot:
 71 
    if ballot:
72 
	trace("\tineffective ballot dropped: %s" % ballot)
 72 
        trace("\tineffective ballot dropped: %s" % ballot)
73 
 
 73 
 
74 
def findLoser(losers, winners, tally):
 74 
def findLoser(losers, winners, tally):
75 
    cMin = sys.maxint  # least number of votes for candidate loser
 75 
    cMin = sys.maxint  # least number of votes for candidate loser
76 
    lMin = []          # list of candidates with least votes
 76 
    lMin = []          # list of candidates with least votes
77 
    for c in tally.keys():
 77 
    for c in tally.keys():
78 
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
 78 
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
79 
	    if len(tally[c]) == cMin:
 79 
            if len(tally[c]) == cMin:
80 
		lMin.append(c)
 80 
                lMin.append(c)
81 
	    else:
 81 
            else:
82 
		lMin = [c]
 82 
                lMin = [c]
83 
		cMin = len(tally[c])
 83 
                cMin = len(tally[c])
84 
    trace("\nELIMINATING LOW CANDIDATE RANDOMLY FROM %s" % lMin)
 84 
    trace("\nELIMINATING LOW CANDIDATE RANDOMLY FROM %s" % lMin)
85 
    if len(lMin) == 0:
 85 
    if len(lMin) == 0:
86 
        return None
 86 
        return None
87 
    else:
 87 
    else:
88 
        return random.choice(lMin)
 88 
        return random.choice(lMin)
89 
 
 89 
 
90 
def redistributeLoser(loser, losers, winners, tally, quota):
 90 
def redistributeLoser(loser, losers, winners, tally, quota):
91 
    excess = len(tally[loser])
 91 
    excess = len(tally[loser])
92 
    if excess <= 0:
 92 
    if excess <= 0:
93 
	trace("\tno ballots to redistribute")
 93 
        trace("\tno ballots to redistribute")
94 
    else:
 94 
    else:
95 
	trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
 95 
        trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
96 
	while len(tally[loser]) > 0:
 96 
        while len(tally[loser]) > 0:
97 
	    ballot = tally[loser][0]
 97 
            ballot = tally[loser][0]
98 
	    tally[loser] = tally[loser][1:]
 98 
            tally[loser] = tally[loser][1:]
99 
	    redistributeBallot(ballot, loser, winners, losers, tally)
 99 
            redistributeBallot(ballot, loser, winners, losers, tally)
100 
    traceTally(quota, tally)
 100 
    traceTally(quota, tally)
101 
    return
 101 
    return
102 
 
 102 
 
103 
def traceTally(quota, tally):
 103 
def traceTally(quota, tally):
104 
    global fTrace
 104 
    global fTrace
Line 125... Line 125...
125 
 
 125 
 
126 
    trace("INPUT SUMMARY")
 126 
    trace("INPUT SUMMARY")
127 
    trace("\t%d ballots" % nBallots)
 127 
    trace("\t%d ballots" % nBallots)
128 
    trace("\tChoosing %s winners" % nWinners)
 128 
    trace("\tChoosing %s winners" % nWinners)
129 
    trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
 129 
    trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
130 
	  (nBallots, nWinners, quota))
 130 
          (nBallots, nWinners, quota))
131 
 
 131 
 
132 
    # Create initial tally
 132 
    # Create initial tally
133 
    #
 133 
    #
134 
    tally = {}
 134 
    tally = {}
135 
    for ballot in ballots:
 135 
    for ballot in ballots: