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 != 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);

        }
    }
}