Counting could be recursive

There are lots of algorithm problems that asks for the count of something. They are mostly combinatorics problems. Those problems usually deal with really big numbers and some common strategies apply to a lot of them.

Talking about combinatorics problems, usually what comes up first to my mind is that “I do not know combinatorics; I have not take the course at Carleton.” There is a math course offered once every two years at Carleton called combinatorics. I did not get a chance to take the course. Thus, when the problem asks me to count, I usually start with a slight panic.

However, after I tried a couple of the problems. I realized that the counting problems, although they deal with really large numbers, are not as mathematical as I thought they were. There are some methods that could be used to a lot of the algorithm problems without being an expert on combinatorics.

The most important one I am going to talk about is recursion. The relation of the number of counting with respect to the input could be recursive. It does not mean that the algorithm needs to be implemented with recursion; it means that there might be some useful recursive relation between the output for this problem and the output for a smaller problem. We can take advantage of the recursive relation to implement a dynamic programming algorithm or even a greedy algorithm, which runs much faster than enumerating all possible solutions.

I should start with a problem called k-inverse-pairs array on Leetcode. The problem asks how many arrangements of 1 to n having k inverse pairs. An inverse pair is an occasion that a number comes later is greater than a number comes before it. For example, if we have n = 4, the numbers are 1,2,3,4 and k = 2. We are looking for the number of arrangements of 1,2,3,4 that have 2 inverse pairs. They are

3,1,2,4

2,3,1,4

1,3,4,2

2,1,4,3

1,4,2,3

Thus the answer when n = 4, k = 2 is 5. There are five inverse pairs. Knowing that the point of this post is that counting could be recursive, how to find the recursive relation between the solution for n, k and a set of smaller problems?

First of all, we notice that the max inverse pair is generated when all the numbers are reverted, like when 1,2,3,4 are arranged as 4,3,2,1. There will be n * (n – 1) / 2 inverse pairs generated. Thus, when k is greater than n * (n – 1) / 2, the answer must be zero. When k is equal to n * (n – 1) / 2, the answer must be 1.

Second, we will observe some cases with small n. When n is 1, there is no inverse pair so the answer is zero no matter what. When n is 2, we have 1,2. Thus, when n is 0, we have 1, when n is 1, we have another 1. Those considerations could serve as the base case for our recursive relations.

Third, based on the considerations that we are looking for a recursive relation, we are attacking the main point: the relation between the solution of a general n, k that does not belong to either of the two points above and a smaller problem. We will use ans(n ,k) to denote the generic answer when the input is n and k, where n is greater than 1 and k is less than or equal to n * (n – 1) / 2. We should consider the recursive relation like this: say that we have all the solutions to the all the subproblems with n – 1 elements, What can we do with the last element to make it a solution to the n, k solution?

If we take a solution of n – 1, k. We can just put n at the end of the arrangement to make it a solution of n, k since there are already k inverse pairs in the original array and we append the last element to the end so that no more inverse pair is created. This should allow us to create ans(n – 1, k) solutions. Next, if we take a solution of n – 1, k – 1, we can insert n to the second to the last element so that one more inverse pair is created. That gives us another ans(n – 1, k – 1) solutions. We can generate all the solutions in this manner, following the cases when the last element generates 0, 1, 2… inverse pairs.

However, when we are going down the cases, there are two different restrictions that could end it. First, n can not create more than n – 1 inverse pairs. In other words, it can not be put at a place before the first element. When it is put to the beginning, n – 1 inverse pairs are created. It can not go over that. Second, n can not generate more than k inverse pairs. If n alone generates more inverse pairs than needed for our problem, that is not going to be a solution. We stop whenever either of the two restrictions ends the sum.

By this, we have the recursive solution as such

ans(n , k) = sum(ans(n – 1, i), i, max(0, k – n + 1), k).

It sums ans(n – 1, i) with i going from max(0, k – n + 1) to k. The max of 0 and k – n + 1 reflects the two restrictions we mentioned in the previous paragraph. i is the number of inverse pair of the n – 1 elements. Zero indicates that it can not create less than 0 inverse pairs; in other words, the last element can not create more than k inverse pairs. The k – n  + 1 reflects the restriction that the last element can not create more than n – 1 inverse pairs, in which case the rest of the n – 1 elements will create k – n + 1 inverse pairs.

At this point, we are at a good position in terms of theoretical analysis of the problem. We have a polynomial solution based on a recursive relation. Obviously, we can implement the algorithm with dynamic programming. However, there are two details to note.

  • When implemented in DP, the algorithm could make use of calculate sum, such as ans(n, k – 1), instead of summing from 0 to the max all the time. That reduces the running time from n cube to n square.
  • The problem requires modulo 10^9 + 7, which is a, though reasonable, but tricky requirement. If we do the modulo each time after we calculate the sum, we may risk going over the limit of integers. That would give us negative numbers. Thus, we have to use a long to temporarily store the sum and then do the modulo and convert it back to int.

From this problem, the most important thing we learned is that counting can be done recursively such as with DP, not just with brute-force enumeration. Another similar problem to look at is find the derangement of an array, which reflects exactly the same idea.

Categories: CS

Leave a Reply

Your email address will not be published. Required fields are marked *