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); } } }

Last updated: Thu Aug 11 10:19:56 EDT 2022.