Link Search Menu Expand Document

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

Nov 2
Recursive Enumeration
BJP 12.5
  1. Trace the execution of programs that recursively build-up solutions.
  2. Define public/private paired recursive enumeration programs.
Nov 3
SectionRecursive Enumeration
Nov 4
Recursive Optimization
  1. Apply the choose-explore-unchoose pattern to recursively build solutions.
  2. Define public/private paired recursive optimization programs.
Nov 5
SectionRecursive Optimization
Nov 6
Notional Machine
BJP 9.1, 9.2, 9.3, 9.4
  1. Determine the compile-time method signature for a given code snippet.
  2. Determine the method ultimately called at runtime for a given code snippet.

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”.

What are three possible solutions to the fourAB problem?
  • aaaa
  • abba
  • babb

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

aaaaabaabaaabbaa
aaabababbaabbbab
aabaabbabababbba
aabbabbbbabbbbbb
What patterns do you notice in the above table?
  • The first two columns have solutions that only start with an “a”.
  • The first column only has solutions that start with “aa”.
  • The first column, first two entries only has solutions that start with “aaa”.
  • The very first entry is “aaaa”.

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”.
a b aa ab aaa aab aaaa aaab