50plus.py

from copy import copy
import random
import numpy
import math

def generate_candidates(length, gender_quota):
    k = 0
    results = {}
    quota = int(math.ceil(length * gender_quota / 100))
    for i in xrange(length):
        kind = 'm'
        if k < quota:
            kind = 'f'
            k += 1
        if kind not in results:
            results[kind] = []
        votes = random.randrange(100)
        results[kind].append(votes)
    results['m'] = sorted(results['m'], key=lambda x: -x)
    results['f'] = sorted(results['f'], key=lambda x: -x)
    return results


def sort_candidates(results, sort_block_fn):
    i = 0
    l = []
    step = 5
    r = copy(results)
    block = []
    while i < len(results['m'] + results['f']):
        block, r = sort_block_fn(r, step, block)
        l.append(block)
        i += step
    return [c for block in l for c in block]


def shift(results, kind):
    v = (kind, results[kind][0])
    results[kind] = results[kind][1:]
    return (results, v)


def __default_shift(results, count):
    v = None
    if len(results['m']) == 0 or count['m'] > 2:
        if len(results['f']) == 0:
            results, v = shift(results, 'm')
        else:
            results, v = shift(results, 'f')
    elif len(results['f']) == 0 or count['f'] > 2:
        if len(results['m']) == 0:
            results, v = shift(results, 'f')
        else:
            results, v = shift(results, 'm')
    else:
        if results['m'][0] >= results['f'][0]:
            results, v = shift(results, 'm')
        else:
            results, v = shift(results, 'f')
    return (results, v)


def as_default_block(results, length, previous_block):
    block = []
    count = {
        'm': 0,
        'f': 0,
    }
    for i in xrange(length):
        if len(results['m']) == 0 and len(results['f']) == 0:
            break
        results, v = __default_shift(results, count)
        if v:
            block.append(v)
            count[v[0]] += 1
    return (block, results)


def as_50plus_block(results, length, previous_block):
    block = []
    count = {
        'm': 0,
        'f': 0,
    }
    for i in xrange(length):
        v = None
        if len(results['m']) == 0 and len(results['f']) == 0:
            break
        if len(block) > 0 and block[-1][0] == 'm' and len(results['f']) > 0 and count['f'] < 2:
            results, v = shift(results, 'f')
        elif len(block) == 0 and len(previous_block) > 0 and previous_block[-1][0] == 'm' and len(results['f']) > 0:
            results, v = shift(results, 'f')
        else:
            results, v = __default_shift(results, count)
        if v:
            block.append(v)
            count[v[0]] += 1
    return (block, results)


def benchmark(length, quota):
    mmpp = []
    mmdd = []
    for i in xrange(10000):
        results = generate_candidates(length, quota)
        as_default = sort_candidates(results, as_default_block)
        as_50plus = sort_candidates(results, as_50plus_block)
        max_pos = None
        mods = 0
        for i in xrange(len(as_default)):
            if as_default[i][0] != as_50plus[i][0] and as_50plus[i][0] == 'f':
                if not max_pos:
                    max_pos = i + 1
                mods += 1
        if not max_pos:
            max_pos = len(as_default)
        mmpp.append(max_pos)
        mmdd.append(mods)
    print("length=%d, quota=%d%%, median(max_pos)=%f, median(mods)=%f" % (length, quota, numpy.median(mmpp), numpy.median(mmdd)))


if __name__ == '__main__':
    benchmark(83, 40)
    benchmark(83, 50)
    benchmark(83, 60)