Data Structure and Algorithm Design II

Chapter 8

Xingang (Ian) Fang

Sections

Combinatorics
Combinatorics in C++

Combinatorics And Counting

Xingang (Ian) Fang

Overview

Combinatorics is a branch of mathematics that deals with counting, arrangement, and combination of objects. It is about finding ‘how many’ possible structures of a certain kind exist. Combinatorics provides tools to answer questions like:

How many ways can a set of objects be arranged?
How many combinations or selections can be made from a group?

Significance

Applications in CS.

Analyze the complexity of algorithms
Design efficient algorithms
Develop data structures that can efficiently store and retrieve data
Solve problems in cryptography, machine learning, and other areas of computer science

Counting Principles

The Sum Rule:
- Mutually exclusive events.
- Example: If you are allowed to choose one from 3 shirts and 4 pants, then you have a total of \(3+4=7\) different pieces of clothing to choose from.
The Product Rule:
- Independent events happening together.
- Example: Using the same clothing example, if you want to decide on an outfit combination of one shirt and one pants out of the 3 shirts and 4 pants, then you have \(3×4=12\) possible combinations to choose from.

Counting Principles (cont.)

The Division Rule:
- Correct constant overcounting.
- Example: If you count n edges of a polygon by starting vertex and ending vertex, then each edge is counted twice. So, the number of edges is n/2.
Include-exclude principle
- Correct the overcounting that occurs when summing up sets with overlapping.
- Two sets \(|A \cup B| = |A| + |B| - |A \cap B|\)
- Three sets \(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|\)

Counting Principles (cont.)

Pigeonhole principle

If n items are put into m containers, with \(n>m\), then at least one container must contain more than one item.
Recurrence relations

Count sub-problems and combine the results to get the final answer.

Credit: https://en.wikipedia.org/wiki/Pigeonholing

Category of problems

Arrangement
- Ordering and organizing objects
- Permutation (order matters)
  - standard
    - all objects: \(P^n = n!\)
    - r objects: \(P^n_r = \frac{n!}{(n-r)!}\)
  - circular
    - all objects: \((n-1)!\)
    - r objects: \(C^n_r \times (r-1)!\)
  - allow repetition
    - r objects: \(n^r\)
  - multi-set
    - all objects with multiple duplicate sets
    - \(\frac{n!}{n_1!n_2!...n_k!}\)

Category of problems (cont.)

Selection (order does not matter)
- Selecting objects from a set
- Order does not matter
- Combination
  - Find permutation first, then divide by r! to correct overcounting
  - standard \(C^n_r = \frac{n!}{r!(n-r)!}\)
  - allow repetition \(\frac{(n+r-1)!}{r!(n-1)!}\)
- Subset
  - Number of all subsets \(2^n\)
  - \(\sum_{k=0}^n C^n_k = 2^n\)

Category of problems (cont.)

Distribution (Partition)
- Distributing objects into groups
- Distributing n identical objects into r distinct groups
  - \(C^{n+r-1}_n\)
- Distributing n distinct objects into r distinct groups
  - \(r^n\)
- Integer partition - represent integer n as sum of positive integers (value up to k)
  - \(p(n,k) = p(n,k-1) + p(n-k,k)\)
  - recursive algorithm
  - hard to find closed form solution in math
Geometric counting

Correct Overcounting In Selection

Example. Select 3 letters from A, B, C, D. Order does not matter.
To solve the problem a good strategy is to first find the number of permutations and then divide by the number of ways to arrange the 3 letters.

Each row represent all permutations of a unique combination. As each row have \(3!\) permutations, using the division rule, we can correct the overcounting.
The final result is \(C^4_3 = P^4_3/P^3_3 = 4\).

Some Strategies

Direct counting
Break down into cases
- sum - exclusive events
- product - independent events
Counting by complement
- \(Count = Total - \overline{Count}\)
Counting by recursion
- May resort to an algorithm

Solve Combinatorics Problems

Identify the type of problem
- Arrangement
- Selection
- Distribution/Partition
Identify the constraints
- Repetition
- Order
- Grouping
Identify the counting principle

Ron’s Greasy Spoon

Build your own breakfast from the menu:
- 1 egg dish 4 choices: Scrambled, Fried, Poached, Omelette
- 2 sides 5 choices: Bacon, Sausage, Hash Browns, Toast, Pancakes
- 1 drink 4 choices: Coffee, Tea, Milk, Orange Juice
How many different breakfasts can you order?
- Product rule: choose 1 egg dish, 2 sides, 1 drink, independent events
- Choose 1 egg dish: 4 ways
- Choose 2 sides: \(C^5_2 = 10\) ways
- Choose 1 drink: 4 ways
- Total number of breakfasts: \(4 \times 10 \times 4 = 160\)

Anagram

An anagram of a string is another string that contains the same characters, possibly in a different order. For example, “listen” can be rearranged to form “silent” or “enlist”, making them anagrams.
Question: How many anagrams of the word “mississippi” are there?
- Order matters: permutation
- Repetition: 4 i’s, 4 s’s, 2 p’s
- Division rule to correct overcounting
  - E.g. The order of the 4 i’s does not matter, so divide by 4!
Total number of anagrams: \(\frac{11!}{4!4!2!} = 34650\)

How many ways to give 5 gifts of the same type to 3 children?

This is a partition problem to distribute 5 identical items to 3 distinct bins.
The well-known method called “star and bar”:
- The idea is to put 5 items (*) together with 2 separators (|) in a line like: * * * | * *|.
- Out of the total 7 positions, pick 5 positions to put the stars.
A less efficient method is to use the sum rule and break down into cases. Calculate the number of ways for various partitions of 5 items into 3 bins. Like 5-0-0, 4-1-0, 3-2-0, 3-1-1, etc. Then add them up.

Poker Problems♠️

To find number of possible hands when you draw 5 random cards.
Total number of possible hands:
- 5 cards from 52 cards
- \(C^{52}_5 = 2598960\)
Royal flush: 1 each suit, 4 total
Straight flush: 36 ways
- 5 consecutive cards, same suit
- Select starting card from Ace, 2, … to 10 10 ways per suit: \(C^{10}_{1}\)
- Select suit: \(C^{4}_{1}\)
- Remove over counting: royal flush
Four of a kind: 624 ways
- Select 2 ranks (order matters): \(P^{13}_{2}\)
- Select a suite for 1 rank: \(C^{4}_{1}\)

Poker Problems (cont.)

Full house: 3744 ways
- Select 2 ranks from 13 ranks (order matters) \(P^{13}_{2}\)
- Select 3 suits for the 3 cards: \(C^{4}_{3}\)
- Select 2 suits for the 2 cards: \(C^{4}_{2}\)
Flush: 5108 ways
- Select 5 ranks from 13 ranks: \(C^{13}_5\)
- Select a suit: \(C^{4}_{1}\)
- Remove overcounting: straight flush, royal flush
Straight 10200 ways
- Product rule
- Select the starting card: \(C^{10}_{1}\)
- Select the suits for each card (repetition allowed) : \(4^5\)
- Remove overcounting: straight flush, royal flush

Poker Problems (cont.)

Three of a kind: 54912 ways
- Product rule
- Select a rank for 3 cards: \(C^{13}_{1}\)
- Select the suits for 3 cards: \(C^{4}_{3}\)
- Select 2 ranks for the other 2 cards: \(C^{12}_{2}\)
- Select the suits for the other 2 cards: \(4^2\)
Two pairs: 123552 ways
- Product rule
- Select 2 ranks for the pairs: \(C^{13}_{2}\) ways
- Select 1 rank for the other card: \(C^{11}_{1}\) ways
- Select 2 suits for the first pair: \(C^{4}_{2}\) ways
- Select 2 suits for the second pair: \(C^{4}_{2}\) ways
- Select 1 suit for the other card: \(C^{4}_{1}\) ways
One pair 1,098,240 ways (exercise)
High card
- Hard to count directly because of the many cases of overcounting
- Use complement: Total - all other hands

Poker Problems (cont.)

It is more common to calculate with partial hands.
The rule:
- Anything you do not know is assumed to be equally likely to be any of the remaining cards.
With two spades in hand? How many ways to get a flush?
- 3 spades in the remaining 11 spades
- \(C^{11}_{3} = 165\)
Two Aces in hand? How many ways to get a full house?
- Case 1: 1 Ace and a pair
  - Select 1 Ace (2 left): \(C^{2}_{1}\)
  - Select 1 rank for the pair: \(C^{12}_{1}\)
  - Select 2 suits for the pair: \(C^{4}_{2}\)
- Case 2: 3 of a kind
  - Select 1 rank for the 3 of a kind: \(C^{12}_{1}\)
  - Select 3 suits for the 3 of a kind: \(C^{4}_{3}\)
- Add the two cases because they are exclusive

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

Related C++ Features (cont.)

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

Order matters? Yes
Repetition allowed? Yes
Size of problem? 10
Type of problem? Permutation with repetition
Counting principle? Product rule
Formula? \(10^{10}\)
Goal? Enumerate
Write code? Yes
Algorithmic paradigm? 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

Find the number of ways to partition a positive integer \(n\) using positive integers \(\leq k\).
Recurrence relation \(p(n, k) = p(n - k, k) + p(n, k - 1)\).
Not easy to solve using math.

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

Data Structure and Algorithm Design II

Sections

Combinatorics And Counting

Overview

Significance

Counting Principles

Counting Principles (cont.)

Counting Principles (cont.)

Category of problems

Category of problems (cont.)

Category of problems (cont.)

Correct Overcounting In Selection

Some Strategies

Solve Combinatorics Problems

Ron’s Greasy Spoon

More problems 1

Anagram

How many ways to give 5 gifts of the same type to 3 children?

Poker Problems♠️

Poker Problems (cont.)

Poker Problems (cont.)

Poker Problems (cont.)

Combinatorics Problems That Needs Algorithms

Why Writing Algorithms?

Typical Approaches

Related C++ Features

Related C++ Features (cont.)

Enumerate All US Phone Numbers

Integer Partition Problem