Black's or Nanson's voting algorithm

vote.py

import sys

#
# MIT Licensed code by Alexander R Pruss
#

# Implements Black's Procedure: Condorcet backed up with Borda to generate a ranked list from ranked votes
# and Nanson's Method: drop all candidates with Borda scores below average
#
# require n [default: None]
#       require a valid ballot to have n candidates
# invariantBordaScoreInBlacks 1/0  [default: 0]
#       in Black's procedure, is the Borda score based on the original ballots (or on the ballots with previous winners deleted)?
# ballot c1 c2 c3 ...
#       register a ballot
# key k name
#       register k as the abbreviation for name
# BEGIN sectionname
# ...
# END sectionname
#       same as prefacing each line of ... with sectionname

candidates = set()
ballots = []
validBallots = []
options = {}
selected = set()
keys = {}
section = None

INVARIANT_BLACKS = "invariantbordascoreinblacks"

def parse(s):
    try:
        return int(s)
    except:
        return s

def beatsInBallot(c1,c2,ballot):
    try:
        i1 = ballot.index(c1)
    except:
        i1 = len(ballot)
    try:
        i2 = ballot.index(c2)
    except:
        i2 = len(ballot)
    return i1 < i2

def isCondorcet(c):
    for d in candidates:
        if d != c and d not in selected:
            beats = 0
            beaten = 0
            for b in validBallots:
                if beatsInBallot(c,d,b):
                    beats += 1
                elif beatsInBallot(d,c,b):
                    beaten += 1
            if beats <= beaten:
                return False
    return True
    
def getGroup(size, soFar=[]):
    if size > len(candidates):
        raise "There aren't enough candidates"
    if len(soFar) == size:
        yield soFar
    else:
        for c in candidates:
            if c not in soFar:
                for g in getGroup(size, soFar+[c]):
                    yield g
    
def winnerGroupOfSize(size):
    global selected
    for group in getGroup(size):
        selected = group
        beaten = False
        for c in group:
            if not isCondorcet(c):
                beaten = True
                break
        if not beaten:
            return group
    return None
    
def describe(c):
    if c in keys:
        return "%s [%s]" % (keys[c],c)
    elif not keys:
        return c
    else:
        return "["+c+"]"

def getCondorcet():
    for c in candidates:
        if c not in selected:
            if isCondorcet(c):
                return c
    return None            
        
def getReversedBordaScore(c,allowed):
    score = 0
    for b in validBallots:
        b = [d for d in b if d in allowed]
        try:
            score += b.index(c)
        except:
            score += len(b)
    return score
    
def getBordas():
    scores = {}
    allowedCandidates = candidates if options.get(INVARIANT_BLACKS,0) else candidates-selected
    for c in candidates:
        if c not in selected:
            scores[c] = getReversedBordaScore(c, allowedCandidates)
            
    best = min(scores[c] for c in scores)
    return [c for c in scores if scores[c] == best]

def BlacksProcedure():
    place = 0
    while len(selected) < len(candidates):
        if len(candidates) - len(selected) == 1:
            c = list(candidates-selected)[0]
            print("position %s: %s" % ( (place+1), describe(c)))
            selected.add(c)
        else:
            c = getCondorcet()
            if c:
                print("position %s (Condorcet): %s" %( (place+1), describe(c)))
                selected.add(c)
                place += 1
            else:
                b = getBordas()
                n = len(b)
                b.sort()
                for c in b:
                    print("position %s (Borda%s score): %s" % ((place+1), ("" if n==1 else " tie"), describe(c)))
                    selected.add(c)
                place += n

def getNansons(candidates):
    scores = { c:getReversedBordaScore(c, candidates) for c in candidates }
    values = [ scores[c] for c in candidates ]
    if min(values) == max(values):
        return list(candidates)
    total = sum(scores[c] for c in candidates)
    n = len(candidates)
    return getNansons([c for c in candidates if scores[c] * n <= total])

def NansonsMethod():
    place = 0
    unselected = set(candidates)
    while len(unselected)>1:
        cond = getCondorcet()
        b = getNansons(unselected)
        n = len(b)
        b.sort()
        for c in b:
            print("position %d%s%s: %s" % ((place+1), (" (Condorcet)" if c == cond else ""), ("" if n==1 else " (tie)"), describe(c)))
            selected.add(c)
            unselected.remove(c)
        place += n
    if len(unselected):
        print("position %s: %s" % ((place+1), describe(list(unselected)[0])))
    
with open(sys.argv[-1]) as f:
    for line in f:
        line = line.strip()
        if '#' in line:
            line = line[:line.index('#')].strip()
        if line:
            cmd,data1 = line.split(None, 2)[:2]
            if cmd == "BEGIN":
                if section:
                    print("Nested sections not allowed")
                    sys.exit(1)
                else:
                    if data1 == "ballots" or data1 == "keys":
                        section = data1[:-1]
                    else:
                        section = data1
            elif cmd == "END":
                if section != data1 and section + "s" != data1:
                    print("END doesn't match BEGIN")
                    sys.exit(1)
                section = None
            else:
                if section:
                    line = section + " " + line
                cmd,data = line.split(None, 1)
                cmd = cmd.lower()
                if cmd == "ballot":
                    ballots.append(data.split())
                elif cmd == "key":
                    dd = data.split()
                    keys[dd[0]] = dd[1]
                else:
                    options[cmd] = parse(data.strip())
                
i = 1                
while i + 1 < len(sys.argv):
    if sys.argv[i].startswith("-o"):
        opt,d = sys.argv[i][2:].split("=", 1)
        options[opt.lower()] = parse(d)
    i+=1
                
print("Options:",options)

def validate(b):
    r = options.get('require',0) 
    if  r and len(b) != r:
        return False
    if len(set(b)) != len(b): 
        # repetition of a candidate
        return False
    return True

validBallots = []
for b in ballots:
    if validate(b):
        validBallots.append(b)
    else:
        print("Invalid ballot:",b)
        
print("Ballots:", len(ballots))
print("Valid ballots:", len(validBallots))
    
for b in validBallots:
    candidates |= set(b)
    
if not candidates:
    print("No candidates!")
    exit(0)

lc = list(candidates)
lc.sort()
print("Candidates:", lc)

m = options.get("method", "Black's")
if m.lower().startswith("black"):
    print("Method: Black's%s" % (" with invariant Borda scores" if options.get(INVARIANT_BLACKS, 0) else ""))
    BlacksProcedure()
elif m.lower().startswith("nanson"):
    print("Method: Nanson's")
    NansonsMethod()
else:
    print("Unknown method %s" % m)

for i in range(1,len(candidates)):
    s = winnerGroupOfSize(i)
    if not s:
        print("No group of %d that Condercet beats everyone else" % i)
    else:
        print(("Group of %d that Condorcet beats everyone else: " % i) + ', '.join(list(sorted(describe(a) for a in s))))