voting.py

## Rampage captain elections

candidates = 'ABCDEFGHIJKLM'

ballots = [
    'HAE',
    'AEC',
    'AGE',
    'ACE',
    'EIC',
    'EAD',
    'DCH',
    'CAL',
    'DAE',
    'AHD',
    'AJD',
    'CKH',
    'CAM',
    'DHG',
    'ECI',
    'AGC',
    'CGD',
    'LAB',
    'DEC',
    'AIC',
    'ACH',
    'CAB',
    'GAC',
    'EDG',
    'EHD',
    'HCA',
    'DFH',
    'DHJ',
    'DEC',
    'ADC',
    'DHA',
    'ACD',
    'AKD',
    'EAD',
    'DKF',
    'GCD',
    'HAE',
    'ECH',
    'DAH',
    'CEA']

preference_matrix = [[0 for c1 in candidates] for c2 in candidates]

## https://en.wikipedia.org/wiki/Schulze_method

## Calculate the preference matrix (the number of ballots where one candidate is preferred to the other).
## In the wikipedia article this is the d[*,*] matrix.
for ballot in ballots:
    for pos, c1 in enumerate(ballot):
        for c2 in candidates:
            pos2 = ballot.find(c2)
            if pos2 == -1 or pos2 > pos:
                preference_matrix[candidates.find(c1)][candidates.find(c2)] += 1

print preference_matrix

# [[0, 25, 20, 22, 22, 25, 24, 21, 25, 25, 25, 24, 25],
#  [0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2],
#  [14, 22, 0, 18, 16, 22, 19, 21, 20, 22, 22, 22, 22],
#  [14, 21, 18, 0, 17, 21, 19, 19, 21, 20, 20, 21, 21],
#  [10, 16, 14, 13, 0, 16, 15, 14, 16, 16, 16, 16, 16],
#  [2, 2, 2, 0, 2, 0, 2, 2, 2, 2, 1, 2, 2],
#  [5, 7, 6, 5, 6, 7, 0, 6, 7, 7, 7, 7, 7],
#  [11, 14, 10, 8, 12, 13, 14, 0, 14, 14, 13, 14, 14],
#  [2, 3, 2, 3, 1, 3, 3, 3, 0, 3, 3, 3, 3],
#  [1, 2, 2, 1, 2, 2, 2, 1, 2, 0, 2, 2, 2],
#  [2, 3, 2, 2, 3, 3, 3, 3, 3, 3, 0, 3, 3],
#  [1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 0, 2],
#  [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]]

## Calculate the strongest path matrix (p[*,*] in the wikipedia article).

path_weight_matrix = []

for c1 in range(len(candidates)):
    row = []
    for c2 in range(len(candidates)):
        if c1 != c2 and preference_matrix[c1][c2] > preference_matrix[c2][c1]:
            row.append(preference_matrix[c1][c2])
        else:
            row.append(0)
    path_weight_matrix.append(row)

for c1 in range(len(candidates)):
    for c2 in range(len(candidates)):
        if c1 != c2:
            for c3 in range(len(candidates)):
                if c1 != c3 and c2 != c3:
                    print 'aaa', c2, c1, c3, path_weight_matrix[c2][c3], min(path_weight_matrix[c2][c1], path_weight_matrix[c1][c3])
                    path_weight_matrix[c2][c3] = max(path_weight_matrix[c2][c3], min(path_weight_matrix[c2][c1], path_weight_matrix[c1][c3]))

print path_weight_matrix

# [[0, 25, 20, 22, 22, 25, 24, 21, 25, 25, 25, 24, 25],
#  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
#  [0, 22, 0, 0, 16, 22, 19, 21, 20, 22, 22, 22, 22],
#  [0, 21, 0, 0, 17, 21, 19, 19, 21, 20, 20, 21, 21],
#  [0, 16, 0, 0, 0, 16, 15, 14, 16, 16, 16, 16, 16],
#  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
#  [0, 7, 0, 0, 0, 7, 0, 0, 7, 7, 7, 7, 7],
#  [0, 14, 0, 0, 0, 13, 14, 0, 14, 14, 13, 14, 14],
#  [0, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 3, 3],
#  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
#  [0, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 3, 3],
#  [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
#  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

## Collect and print results: for each candidate gather the list of candidates that rank lower.

candidates_with_better_than = []

for c1 in candidates:
    better_than = []

    for c2 in candidates:
        if c1 != c2:
            i1 = candidates.find(c1)
            i2 = candidates.find(c2)
            if path_weight_matrix[i1][i2] > path_weight_matrix[i2][i1]:
                better_than.append(c2)

    candidates_with_better_than.append((better_than, c1))

candidates_with_better_than.sort(key=lambda (bt, c): -len(bt))

for bt, c in candidates_with_better_than:
    print c, "is better than", ' '.join(bt)

# A is better than B C D E F G H I J K L M
# C is better than B E F G H I J K L M
# D is better than B E F G H I J K L M
# E is better than B F G H I J K L M
# H is better than B F G I J K L M
# G is better than B F I J K L M
# I is better than B F J L M
# K is better than B F J L M
# L is better than B M
# B is better than M
# F is better than M
# J is better than M
# M is better than