# -------
# ------- banzhaf - version 1.0
# ------- A simple self-contained function to compute the Banzhaf Power Index given:
# -------   * a list of integer weights for all voters in the system, sorted in ascending order
# -------   * the quota for the voting system
# ------- Copyright 2004 Ruben R. Puentedura
# -------
# ------- This software is released under a Creative Commons 2.0 Attribution License:
# -------   You are free:
# -------     * to copy, distribute, display, and perform the work
# -------     * to make derivative works
# -------     * to make commercial use of the work
# -------   Under the following conditions:
# -------     * Attribution. You must give the original author credit.
# -------     * For any reuse or distribution, you must make clear to others the license terms of this work.
# -------     * Any of these conditions can be waived if you get permission from the copyright holder.
# ------- The full legal text for this license is available at:
# -------   http://creativecommons.org/licenses/by/2.0/legalcode
# -------
# ------- Background notes:
# -------   The algorithm used here is based upon the description in:
# -------     Leech, Dennis (2002), "Computation of Power Indices", Warwick Economic Research Papers, Number 644, University of Warwick.
# -------     Available online at:
# -------       http://www.warwick.ac.uk/~ecrac/twerp644.pdf
# -------   A good introduction to the Banzhaf Power Index can be found in:
# -------     Taylor, Alan D. (1995), "Mathematics and Politics: Strategy, Voting, Power and Proof", Springer-Verlag, New York, New York.
# ------- 
# ------- Program notes:
# -------   banzhaf(weight, quota) returns a list containing the Banzhaf Power Index for all voters in the system
# -------     * weight is a list of integer weights for all voters in the system, sorted in ascending order
# -------     * quota is an integer which designates the number of votes needed for a coalition to win
# -------   The program will run in a few seconds for "reasonable" scenarios:
# -------       * total number of voters on the order of up to a thousand or so;
# -------       * maximum number of votes per voter on the order of up to a hundred or so.
# -------   Even many "unreasonable" scenarios will run quickly.
# -------   For scenarios that take too long to run using this code, a Monte Carlo approach may work best - see Leech (2002) for more info.
# ------- 
# ------- Sample code notes:
# -------   To test banzhaf, try calling it with the following parameters:
# -------     test_weight = [1,2,2,4,4,4]
# -------     test_quota = 12
# -------   These parameters correspond to the EEC in 1958 - the members (ordered by increasing voting weight) were:
# -------     Luxembourg, Netherlands, Belgium, Italy, Germany, France
# -------   The result should be:
# -------     test_index = [0.0, 0.14285714285714285, 0.14285714285714285, 0.23809523809523808, 0.23809523809523808, 0.23809523809523808]
# -------   A simple test program, illustrating a "typical" use scenario is included at the end of this file.
# -------


# -------  The banzhaf function

def banzhaf(weight, quota):

    max_order = 0                                  # compute the maximum order for our polynomial
    for each_weight in weight:
        max_order = max_order + each_weight
    
    polynomial = [1] + max_order*[0]               # create a list to hold the polynomial coefficients
    
    current_order = 0                              # compute the polynomial coefficients
    aux_polynomial = polynomial[:]
    for i in range(len(weight)):
        current_order = current_order + weight[i]
        offset_polynomial = weight[i]*[0]+polynomial
        for j in range(current_order+1):
            aux_polynomial[j] = polynomial[j] + offset_polynomial[j]
        polynomial = aux_polynomial[:]
    
    banzhaf_power = len(weight)*[0]                                 # create a list to hold the Banzhaf Power for each voter
    swings = quota*[0]                                              # create a list to compute the swings for each voter
    
    for i in range(len(weight)):                                    # compute the Banzhaf Power
        for j in range(quota):                                      # fill the swings list
            if (j<weight[i]):
                swings[j] = polynomial[j]
            else:
                swings[j] = polynomial[j] - swings[j-weight[i]]
        for k in range(weight[i]):                                  # fill the Banzhaf Power vector
            banzhaf_power[i] = banzhaf_power[i] + swings[quota-1-k]
    
    total_power = 0                                                 # compute the Total Banzhaf Power
    for each_power in banzhaf_power:
        total_power = total_power + each_power
    
    banzhaf_index = len(weight)*[0]                                 # create a list to hold the Banzhaf Power Index for each voter
    
    for i in range(len(weight)):                                    # compute the Banzhaf Power Index
        banzhaf_index[i] = float(banzhaf_power[i])/total_power
    
    return banzhaf_index

# -------  End of banzhaf



# -------  A simple program to illustrate the use of banzhaf

import string

# the weights for the 2004 Electoral College in a dictionary
electoral_college = {'Alabama':9,'Alaska':3,'Arizona':10,'Arkansas':6,'California':55,'Colorado':9,'Connecticut':7,'D.C.':3,'Delaware':3,'Florida':27,'Georgia':15,'Hawaii':4,'Idaho':4,'Illinois':21,'Indiana':11,'Iowa':7,'Kansas':6,'Kentucky':8,'Louisiana':9,'Maine':4,'Maryland':10,'Massachusetts':12,'Michigan':17,'Minnesota':10,'Mississippi':6,'Missouri':11,'Montana':3,'Nebraska':5,'Nevada':5,'New Hampshire':4,'New Jersey':15,'New Mexico':5,'New York':31,'North Carolina':15,'North Dakota':3,'Ohio':20,'Oklahoma':7,'Oregon':7,'Pennsylvania':21,'Rhode Island':4,'South Carolina':8,'South Dakota':3,'Tennessee':11,'Texas':34,'Utah':5,'Vermont':3,'Virginia':13,'Washington':11,'West Virginia':5,'Wisconsin':10,'Wyoming':3}

system_quota = 270                                       # the quota for the Electoral College

items = [(v, k) for k, v in electoral_college.items()]   # we need to sort the data in ascending order by number of votes
items.sort()

electoral_weight = [v for v, k in items]                 # we construct a list with nothing but the weights from the resulting list of tuples...
state_list = [k for v, k in items]                       # ...and a list with nothing but the states

electoral_index = banzhaf(electoral_weight, system_quota)         # we now calculate the Banzhaf Index

# we construct a list of tuples with the state name and the corresponding Banzhaf index and sort it by name
state_electoral_index = [(state_list[i],electoral_index[i]) for i in range(len(state_list))]  
state_electoral_index.sort()

for k, v in state_electoral_index:                                # a printout of our results
     print string.ljust(k, 20), v

state_electoral_index_dictionary = dict(state_electoral_index)    # finally, we put the results back into a dictionary for further use

# -------