# VotingPower.java

Below is the syntax highlighted version of VotingPower.java from §2.3 Recursion.

/******************************************************************************
*  Compilation:  javac Voting.java
*  Execution:    java Voting 7 4 2 6 6
*
*  Computes the voting power of each coalition. John F. Banzhaf III
*  proposed a ranking system for each coalition in a block voting system.
*  Suppose party i control w[i] votes. A strict majority of the votes
*  is needed to accept or reject a proposal. The voting power of party i
*  is the number of minority coalitions it can join and turn it into
*  a winning majority coalition.
*
*  Idea from: http://acm.uva.es/p/v4/435.html
*
*  Sample execution:
*
*     % java VotingPower 7 4 2 6 6
*     party 0 has power index 10
*     party 1 has power index 2
*     party 2 has power index 2
*     party 3 has power index 6
*     party 4 has power index 6
*
* Warning: algorithm uses brute force enumerate and takes time
*          proportional to n 2^n. It uses an int and bit whacking
*          for the enumeration so it wouldn't work for n > 31 anyway.
*
******************************************************************************/

public class VotingPower {
public static void main(String[] args) {
int n = args.length;
int[] w = new int[n];

int sum = 0;
for (int i = 0; i < n; i++) {
w[i] = Integer.parseInt(args[i]);
sum += w[i];
}

for (int i = 0; i < n; i++) {
// compute voting power of party i
int power = 0;

// swap i with index 0
int temp = w[0];
w[0] = w[i];
w[i] = temp;

// enumerate remaining coaltions
for (int coalition = 0; coalition < (1 << n); coalition += 2) {

// determine votes for parties j that are in coalition
for (int j = 1; j < n; j++)
if ((coalition >> j) % 2 != 0) votes += w[j];

// check if i turns coalation into majority
if ((votes <= sum / 2) && (votes + w[0] > sum / 2))
power++;
}
StdOut.println("party " + i + " has power index " + power);

}
}
}