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) {
            int votes = 0;

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

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

      }
   }
}