Combinatorics Problems That Needs Algorithms

Demonstrated in C++

Why Writing Algorithms?

• Prove correctness of your solution using math
• Too hard to solve using math
• When we want to see the solution in addition to the count

Typical Approaches

• Strategy: Other algorithmic paradigms
• Enumeration problems
  • Simple enumeration: brute force, backtracking
  • With overlapping sub-problems: dynamic programming
• Optimization problems (Combinatorial optimization)
  • Dynamic programming may apply when the problem has overlapping subproblems and the required substructure.
  • A greedy algorithm may apply when a greedy-choice argument establishes that local choices produce the requested optimum.
  • Neither overlap nor its absence alone determines that greedy is suitable.
  • Heuristic algorithms: simulated annealing, genetic algorithm, etc.
  • Linear programming

Related C++ Features

• Recursion
  • art of memorization (manipulate parameter and return value)
• STL algorithms (<algorithm> header)
  • next_permutation function
  • is_permutation function
  • sort function
  • is_sorted function
  • reverse function
  • rotate function
  • shuffle function
• Useful data structures
  • std::vector<bool> (bitset)
    • to memorize visited/processed/seen states
    • small number of total states
    • $\Theta(1)$ time complexity for set and test operations
  • std::set to memorize visited/processed/seen states
    • large number of total states
    • Self-balancing binary search tree
    • $\Theta(\log n)$ time complexity for insert and find operations
    • $\Theta(n)$ time complexity for erase operation
  • std::unordered_set to memorize visited/processed/seen states
    • large number of total states
    • Hash table
    • $\Theta(1)$ time complexity for insert, find, and erase operations

Enumerate All US Phone Numbers

In this problem, we want to enumerate all US phone numbers.

This is a permutation problem that allow repetition. As an enumeration problem, we can solve this problem using brute force.

void enumeratePhoneNumbers(int n, string prefix) {
  if (n == 0) {
    cout << prefix << endl;
    return;
  }
  for (int i = 0; i < 10; i++) {
    enumeratePhoneNumbers(n - 1, prefix + to_string(i));
  }
}

Integer Partition Problem

In this problem we take advantage of the recurrence relation of the integer partition problem. $p(n, k) = p(n - k, k) + p(n, k - 1)$.

int partition(int n, int k) {
  // Base cases
  if (n == 0) return 1;  // One way to partition 0 using no numbers
  if (n < 0 || k <= 0)
    return 1;  // No way to partition with negative number or no numbers left

  // Recursive cases
  // Include k in the partition and recursively partition n-k with k
  int include_k = partition(n - k, k);

  // Exclude k from the partition and recursively partition n with k-1
  int exclude_k = partition(n, k - 1);

  return include_k + exclude_k;
}