# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Proportional Approval Voting implementation
#
# See also C code at [CleanOptPRVote.c](https://rangevoting.org/CleanOptPRVote.c) for a related problem as discussed by RangeVoting\.org at:
# * [Optimal proportional representation Part I:  methods, algorithms, advantages, and inherent flaws](https://rangevoting.org/QualityMulti.html)
# * [Optimal proportional representation Part II: The two classes and the "holy grail"](https://rangevoting.org/NonlinQuality.html)
#
# Todo: When it gets slow
# * use counts of unique cvrs, not all cvrs
# * use multiple threads
# * come up with more efficient algorithm, e.g. A*, which is easily distributed
# * recode in Rust :)

# +
import string
import pandas as pd
import collections
import itertools
import time

import pav
# -

winner, w_cvrs, scores, df = pav.tally_pav("Westminster_Adams.csv", 3)

# Use this to test out new code after modifying the pav module
import importlib
importlib.reload(pav)

df.head()

winner, a_cvrs, scores, df = pav.tally_pav("Byers_SD_32J_Adams.csv", 4)


# # Timing results
#
# Note that the C code at [CleanOptPRVote.c](https://rangevoting.org/CleanOptPRVote.c) has been timed at 4V·Binomial(C,W) nanoseconds.
#
# Based on the result below of 162 seconds for 24 candidates, 12 winners, 121 ballots,
# this code might be perhaps 2 orders of magnitude slower, with a constant multiplier of 500 nanoseconds rather than 4.
#
# Takes about 12 seconds(?) for 20 candidates, 10 winners, 121 ballots
#
# Uses nearly 3 GB of memory with 24 and 12
#
# 24 choose 12 = 2704156

def timepav(candidates, winners, cvrs):
    "Time how long it takes to tally a PAV contest using given cvrs with given number of candidates and winners"

    # If you need more than 62 candidates for some unusual reason, see itertools.product or this infinite recipe: https://stackoverflow.com/a/42099359/507544
    many_candidates = tuple(string.ascii_uppercase + string.ascii_lowercase + string.digits)
    possible_results = itertools.combinations(many_candidates[:candidates], winners)
    t1 = time.time()
    scores = {}
    for result in possible_results:
        resultset = frozenset(result)
        scores[resultset] = sum(pav.utility(resultset, cvr) for cvr in cvrs)
    timings.append("{} seconds for {} candidates, {} winners, {} ballots".format(time.time() - t1, candidates, winners, len(cvrs)))


timings = []

timepav(12, 6, a_cvrs)

timepav(12, 6, w_cvrs)

timepav(14, 7, a_cvrs)

timepav(14, 7, w_cvrs)

timepav(18, 9, w_cvrs)

timings

assert False, "Prevent overwriting of previous results below"

# older results
timings


# # Harmonic / Psi voting
# From [Optimal proportional representation - RangeVoting\.org](https://rangevoting.org/QualityMulti.html)

# Let C=#candidates, V=#voters, W=#winners, 0<W<C<V, and let S_v,c be the real-valued score given by voter v to candidate c on her ballot. Then here is our highly general class of quality measures Q:
#
#
# Q = ∑1≤v≤V F( ∑1≤j≤W [jth greatest S_v,c among winning c] · A_j )
#
# "Harmonic voting.") If F(x)=x, then PR will be assured by choosing A_j = 1/(j-1+Δ) where Δ is any positive constant.
#
# I.e. for delta = 1/2, A_j = 2 * [1, 1/3, 1/5, 1/7, ...]
#
# And for delta = 1, A_j = [1, 1/2, 1/3, 1/4, ...]

def A(j, delta=0.5):
    return 1 / (j - 1 + delta)


[A(j) for j in range(1, 5)]

[A(j, 1.0) for j in range(1, 5)]

# # Older

candidates = 12
winners = 6

many_candidates = tuple(string.ascii_uppercase + string.ascii_lowercase + string.digits)

possible_results = itertools.combinations(all_candidates + tuple(list(range(candidates - len(all_candidates)))), winners)

t1 = time.time()
scores = {}
for result in possible_results:
    resultset = frozenset(result)
    scores[resultset] = sum(pav.utility(resultset, cvr) for cvr in cvrs)
timings.append("{} seconds for {} candidates, {} winners, {} ballots".format(time.time() - t1, candidates, winners, len(cvrs)))

timings

StarcoderdataJupyterScriptsDedupFiltered