Recursive Enumeration

Table of contents

1. Election Simulator
2. Enumeration

Election Simulator

The President of the United States is not elected by a popular vote, but by a majority vote in the Electoral College. Each state, plus DC, gets some number of electors in the Electoral College, and whoever they vote in becomes the next President. Right before the 2016 election, NPR reported that 23% of the popular vote would be sufficient to win the election, based on the 2012 election data. They arrived at this number by looking at states with the highest ratio of electoral votes to voting population. This was a correction to their originally-reported number of 27%, which they got by looking at what it would take to win the states with the highest number of electoral votes. But the optimal strategy turns out to be neither of these and instead uses an unlikely coalition of small and large states.

Election Simulator

How might we identify the coalition of states with the minimum possible popular votes needed to win the Electoral College? So far, all of our programming experience has focused on solving problems that have only one solution (result or output) associated with each input. Sometimes, that solution is a collection type, but even a collection of data still represents only one solution, one coalition of states out of all of the possible combinations. Even generative recursive algorithms still only produce one solution per input, though the algorithm generating them uses randomness.

Enumeration

Recursive enumeration (also known as exhaustive search) is a recursive problem-solving technique that solves problems by systematically enumerating (listing out) all solutions in the solution space. Consider the recursive algorithm fourAB that prints out all strings of length 4 composed only of the letters “a” and “b”.

To enumerate the solutions to fourAB, we can list out the solutions in a table.

By arranging the solutions in an organized structure, we can identify recursive partial solutions.

• The left two columns are associated with prepending an “a” to the start of all a/b strings of length 3.
• The right two columns are associated with prepending a “b” to the start of all a/b strings of length 3.

Recursive enumeration differs from typical recursive algorithms. Unlike structurally-recursive algorithms that break down their inputs into subproblems, enumerating algorithms work backwards by starting with empty data and generating larger and larger partial solutions until a complete solution is obtained.

Outline for defining recursive enumeration algorithms

1. Start the recursive algorithm with empty data.
2. Recursively generate larger partial solutions.
3. At each base case, report the completed solution.

public static void main(String[] args) {
    fourAB("");
}

public static void fourAB(String soFar) {
    if (soFar.length() == 4) {
        System.out.println(soFar);
    } else {
        fourAB(soFar + "a");
        fourAB(soFar + "b");
    }
}

The following (partial) recursive decision tree shows each decision (diamond) made during the execution of the first branch of fourAB.

1. Starting with the empty string, add an “a”.
2. From the string “a”, add another “a”.
3. From the string “aa”, add another “a”.
4. From the string “aaa”, add another “a”.
5. Since “aaaa” is length 4, print “aaaa”.
6. Return back to “aaa”, add a “b”.
7. Since “aaab” is length 4, print “aaab”.
8. …