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