Combinatorics

Combinatorics problems are one of the most fascinating category of DS & Algo. Although the problems looks daunting at first but generally they have an elegant solution at the end.

But very few companies ask problems related to combinatorics mostly due to the fact that some of these problems could be very hard for a candidate to come up with a solution within 30 minutes if the candidates have not seen similar problems before. In this post I have tried to compile some of the ‘easier’ combinatorics problems.

The solution for most of these problems comes under the category of ‘generating functions’ combinatorial problems which are most often solved using recursion or dynamic programming.

Problem 1:

Partitioning group — Given there are N people standing in a queue. Compute the number of ways of dividing the people into K groups such that each group contains at-least one person from the queue. Assume that the ordering of people in a group do not matter ?

What if the ordering of the people in a group also matters ?

Solution:

Let us take out the 1st person and place the remaining N-1 persons. Let S(N, K) denote the number of ways of putting N people into K non-empty groups when ordering doesn't matter.

The 1st person can be put in either an existing group or a new group with only the 1st person.

If the 1st person is added to an existing group, it implies that the number of existing groups is K. Number of ways to achieve this is K*S(N-1, K).

If the 1st person is added to a new group, it implies that the number of existing groups is K-1. Number of ways to achieve this is S(N-1, K-1).

Thus S(N, K) = K*S(N-1, K) + S(N-1, K-1)

Space and run-time complexity is O(N*K).

If the ordering matters, then we cannot solve the problem in the manner above. Let’s say that one of the permutations of N people be denoted as:

p1 p2 … pN

Then in order to create K non-empty groups we put K-1 markers in between N-1 slots in (N-1)C(K-1) ways.

p1 p2 p3 | p4 p5 | p6 | p7 p8 p9 …| … pN-1 pN

But only the ordering of people within a group matters but ordering of groups do not matter. For e.g. 2 groups with (1,2) (3,4) is same as (3,4) (1,2). Thus we divide by K!

Thus number of ways when ordering within a group matters = N!*(N-1)C(K-1)/K!

Problem 2:

In the above problem, assuming that the heights of the people are all unique, how many ways can we partition the N people into K non-empty groups such that the heights on the people in a group are in increasing order ?

Solution:

If we sort the people by their heights then this is same as the previous problem. Note that sorting the people by their heights do not affect the number of ways of grouping as this is only a generalization.

S(N, K) = K*S(N-1, K) + S(N-1, K-1)

Because if we exclude the 1st person, and S(N-1, K) denote the number of ways of forming K non-empty groups with N-1 people with each group sorted by heights, then the 1st person can be added in front of all the K groups because the 1st person has the smallest height.

Problem 3:

There are N towers each of different height. How many permutations are possible such that for exactly K towers, the height is greater than the previous tower ?

Solution:

Let S(N, K) denote the number of ways to arrange the N towers such that for exactly K towers, the height is greater than the previous tower.

We can find a recurrence relation by observing that we can first sort the heights without loss in generalisation.

If the 1st tower (smallest one) is added before any of the towers with height greater than the previous one or at the end, then the number of towers higher than the previous one does not change. Thus if there are K existing towers higher than the previous one, then we can add the smallest tower at K+1 positions in (K+1)*S(N-1, K) ways.

If the 1st tower (smallest one) is added at all other remaining positions i.e. not the slot before any tower higher than the previous tower or at the end, then the number of towers higher than the previous one increases by 1. Thus if there are K-1 existing towers higher than the previous one, then we can add the smallest tower at N-K positions in (N-K)*S(N-1, K-1) ways.

Thus S(N, K) = (K+1)*S(N-1, K) + (N-K)*S(N-1, K-1)

Problem 4:

You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

Solution:

For simplicity let’s assume that we sort the blocks by height. Let S(N, L, R) denote the number of ways to arrange the blocks with L blocks from left and R blocks from right visible.

If we exclude the 1st block and arrange the remaining N-1 blocks, then if the 1st block (smallest block) is added at all positions between the existing 1st and last blocks, then the number of blocks visible from left and right remains same. There N-2 places.

If the smallest block is added before the existing 1st block then the number of blocks visible from left increases by 1 and number of blocks visible from right remains same.

If the smallest block is added after the last block then the number of blocks visible from left remains same and number of blocks visible from right increases by 1.

Thus S(N, L, R) = (N-2)*S(N-1, L, R) + S(N-1, L-1, R) + S(N-1, L, R-1)

Space and Time complexity is O(N*L*R).

Problem 5:

Given n, generate all possible valid parenthesis with n-pairs of ‘(‘ and ‘)’. How many possible valid parenthesis are there with n-pairs ?

What if there is a restriction on the maximum depth of nesting ≤ d ?

Solution:

Since all possible valid parenthesis begins with a ‘(‘, and there must be a corresponding ‘)’, thus all possible valid parenthesis are of the following form:

(A)B

where A is valid parenthesis with 0 or more pairs and B is valid parenthesis with 0 or more pairs and also A+B = n-1 pairs. Let S(n) denote the number of valid parenthesis with n pairs.

Thus S(n) = S(0)*S(n-1) + S(1)*S(n-2) + S(2)*S(n-3) + … + S(n-1)*S(0)

S(i)*S(n-i-1) denotes there are ‘i’ pairs in A and n-i-1 pairs in B.

Space complexity is O(n). Time complexity is O(n²).

With the constraint that maximum depth of nesting ≤ d, we can modify the recurrence relation as follows:

S(n, d) = S(0, d-1)*S(n-1, d) + S(1, d-1)*S(n-2, d) + … + S(n-1, d-1)*S(0, d)

where S(n, d) is the number of valid parenthesis with n pairs and maximum depth of ‘d’.

In the formulation above: (A)B, if the maximum depth is ‘d’, then the maximum depth of A and B is d-1 and d respectively.

Space complexity is O(n*d). Time complexity is O(n*d).

Code to generate all valid parenthesis with n pairs:

These kind of problems comes under the category of Catalan Numbers. There are many other similar problems.

One such problem: Given a coin to toss. Count the number of ways to toss the coin N times such that for each 1 to N, the number of Heads is greater than equal to the number of Tails.

This is similar to parenthesis problem because in parenthesis problem number of left parenthesis ‘(‘ for any k is greater than equal to number of right parenthesis ‘)’.

Some very good resources:

1. http://www.geometer.org/mathcircles/catalan.pdf
2. https://cp-algorithms.com/combinatorics/catalan-numbers.html
3. https://brilliant.org/wiki/catalan-numbers/

Problem 6:

An integer is said to be self-descriptive if it has the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that this digit appears in the number.
Generate all self-descriptive numbers ≤ M, where M ≤ 10⁹

Solution:

One possible solution is to iterate through all numbers 1 to M and for each number check if it is self-descriptive. Checking whether a number is self-descriptive is easy as we only need to store the counts of each integer and check if the count matches with num[i] = count[s[i]], where s[i] is the integer at index i

The time complexity of the above approach is O(M).

We can do better than that by observing that the length of a self descriptive number is equal to the sum of its digits (but not the other way round).

Note that the sum of the counts of the digits must be equal to the length of the number and sum of the counts of the digits in turn is equal to the sum of digits for a self descriptive number.

Thus for length of number N, generate all possible numbers whose sum of digits equals to N and for each number check whether it is self-descriptive or not.

Let S(N, K) denote the numbers of length N whose sum of digits is K. Then we can use Dynamic Programming to generate S(N, K) as shown below.

S(N, K) = [S(N-1, K), S(N-1, K-1), … S(N-1, 0)] for 0 ≤ K ≤9.

What we want is S(N, N)

Problem 7:

Self describing sequence — Given a self describing streaming sequence 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, … where if seq[i] = k, then i+1 occurs k times in seq. Find the i-th number in the sequence. What if ‘i’ is too large ?

Solution:

One solution is to generate the sequence iteratively. Let ‘arr’ be the array of cumulative counts of 1, 2, 3, 4 …. and so on. Let ‘arr’ contain the cumulative counts upto i-1 i.e. arr[0] = number of 1s, arr[1] = number of 1s + number of 2s, arr[2] = number of 1s + number of 2s + number of 3s and so on.

Then for i, the count of ‘i’ can be found by finding an index j s.t. arr[j] ≥ i and arr[j-1] < i. Then the count of ‘i’ is j+1. Update ‘arr’ by adding the count arr[-1]+j+1.

For finding the index j we can do binary search over ‘arr’.

Problem 8:

There are N passengers assigned to N seats in an airplane. Find out the number of ways to take the seats such that none of the passengers takes his/her own seat.

Write a program to generate all such seating arrangements.

Solution:

This problem is same as finding the number of derangements with N numbers.

Let S(N) be the number of derangements with N numbers.

If we consider the element at index 0, then it can be placed at N-1 different indexes (1, 2, … N-1). If the element at index 0 is placed at index i, then we can either

1. Place the element currently at index i at index 0 i.e. swap elements at index 0 and i or
2. Place the element at index i at any other index.

For case 1, there are S(N-2) derangements because we have fixed the indices 0 and i.

For case 2, there are S(N-1) derangements because we have fixed the index only for i.

Thus S(N) = (N-1)*(S(N-1) + S(N-2))

Time complexity is O(N). Space complexity is O(1).

Code to generate all derangements for N:

Problem 9:

A bowl of spaghetti contains N strands. Ravi picks two ends at random and joins them together. He does this until no ends remain. Compute the number of ways Ravi can make K loops.

Assume that strands are distinguishable but 2 ends of the same strand are indistinguishable.

Solution:

Let S(N, K) be the number of ways Ravi can make K loops using N strands i.e. 2N ends.

There are 2 possible ways Ravi can select 2 ends:

1. Ravi selects 2 ends of the same strand. Then he has created 1 loop and there are N-1 strands remaining. Ravi can select 2 ends of the same strand in N ways.
2. Ravi selects 2 ends of different strands. Then he has not created any loop and still there are N-1 strands remaining because after joining 2 ends of different strands, it is now equivalent to a single strand with 2 open ends. Ravi can select 2 ends of different strands in 2N*(N-1) ways because after he selects 1 end he can select the other end in 2N-2 ways (2 ends from N-1 remaining strands). But selecting ends i-j is equivalent to selecting ends j-i. Thus number of ways is 2N*(2N-2)/2=2N*(N-1)

This can be computed in another way. There are 2N ends. Thus there are 2N*(2N-1)/2 ways to select 2 ends. But N ways to select 2 ends of same strand. Thus remaining N*(2N-1)-N=2N*(N-1) ways to select 2 ends of different strands.

Thus S(N, K) = N*S(N-1, K-1) + 2N*(N-1)*S(N-1, K)

Space and time complexity is O(N*K).

Problem 10:

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical and if an egg breaks, you cannot drop it again. You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break. Each move, you may take an egg and drop it from any floor X (with 1 <= X <= N). Your goal is to know what the value of F is.

What is the minimum number of moves required ?

Solution:

Let H(N, K) be the minimum number of moves required to find the floor F with N floors and K eggs.

Optimal strategy is to choose a starting floor such that number of moves remaining is minimum.

If we choose i-th floor as the starting floor, then there are 2 scenarios:

1. Egg breaks — Then there are H(i-1, K-1) remaining moves.
2. Egg do not break — Then there are H(N-i, K) remaining moves.

We will take the maximum of these 2 paths.

For e.g. if the minimum number of steps required if F=10 is 7, F=4 is 5 and F=13 is 6, then given 7 steps we can find all the 3 floors (since only one floor F will be valid at a time). Thus we take the maximum.

Then we take the minimum across all i as follows:

H(N, K) = 1 + min(max(H(0,K-1), H(N-1,K)), max(H(1,K-1), H(N-2,K)), … max(H(N-1,K-1), H(0,K))).

Time complexity is O(N²K). Space complexity is O(N*K)

We can improve this by noticing that if we increase the number of floors N, then number of moves also increases and decreasing N, decreases the number of moves.

Thus we can do binary search on the number of moves.

Let H(X, K) be the maximum number of floors possible to cover with X moves and K eggs.

If at any floor, an egg breaks, then we can cover maximum of H(X-1, K-1) floors below this floor. If the egg do not break then we can cover maximum of H(X-1, K) floors above this floor. Note that this is irrespective of which floor I have chosen to drop an egg.

Thus form any floor we can cover H(X-1, K-1) + H(X-1, K) floors.

Thus H(X, K) = H(X-1, K-1) + H(X-1, K) + 1 (adding 1 because we have to also consider the floor from which I am dropping the egg).

Thus for a given X we compute H(X, K), if H(X, K) < N, then we increase X else if H(X, K) ≥ N we decrease X.

Using binomial coefficients we can derive that:

H(X, K) = (X choose 1) + (X choose 2) + … + (X choose K)

Time complexity is O(K*logN). Space complexity is O(1).