Programmer: Recursion

An excerpt from wiki (http://en.wikipedia.org/wiki/Catalan_number):

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects.

The first Catalan numbers for n = 0, 1, 2, 3, … are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

Some of the applications are:

C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

((())) ()(()) ()()() (())() (()())

C_n is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator). For n = 3, for example, we have the following five different parenthesizations of four factors:

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

Successive applications of a binary operator can be represented in terms of a full binary tree.^[3] (A rooted binary tree is full if every vertex has either two children or no children.) It follows that C_n is the number of full binary trees with n + 1 leaves:

If we want to print all the possible balanced parenthesis - we can solve by below recursive function which prints either "(" or ")" recursively - but while printing make ")" it makes sure that the number of left "(" printed are always >= to number of right parenthesis.

Below is the corresponding code

Code Snippet

string[] GetAllPossibleParanthesis_2(int N)
        {
            var r = this.GetAllPossibleParanthesis_2(N, N, "");
            return r;
        }
        string[] GetAllPossibleParanthesis_2(int left, int right, string s)
        {
            if((left == 0) && (right==0))
            {
                return new string[] { s };
            }
            Assert.IsTrue(left <= right);
            List<string> results = new List<string>();
            if (left > 0)
            {
                var r = this.GetAllPossibleParanthesis_2(left - 1, 
                    right, s + "[");
                results.AddRange(r);
            }
            if(left <= (right-1))
            {
                var r = this.GetAllPossibleParanthesis_2(left,
                    right-1, s + "]");
                results.AddRange(r);
            }
            return results.ToArray();
        }

Example of how the recursive method generates balanced parenthesized string for 3 pairs

Solving the problem identifying the Catalan recursive relationship

The Catalan numbers satisfy the recurrence relation

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;

for ex, C_n is the number of different ways n + 1 factors can be completely parenthesized
i.e; C0 = 1 (1 factor -> a)
      C1 = 1 (2 factors -> (ab))
      C2 = 2 (3 factors -> (a(bc)), ((ab)c)
Or, C2 = C0*C1 + C1*C0 = { a(bc), (ab)c }
      C3 = 5 (4 factors -> (a(b(cd)), (a((bc)d)), ((ab)(cd)), (((ab)c)d), ((a(bc))d)
Or, C3 = c0*c2 + c1*c1+c2*c0 { a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d

Note: its probably more intuitive from programming perspective if we start the sequence with notation c1 than c0 where c1 represents different ways '1' factor can be completely parenthesized and so on...

Below is the corresponding code where factors are sent as string to the method:

Code Snippet

string[] CatalanNumber_GeneratingParanthesizedFactors(string s)
        {
            s.ThrowIfNullOrWhiteSpace("s");
            if(s.Length == 1)
            {
                return new string[] {s};
            }
            var r = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                s);
            return r;
        }
        string[] CatalanNumber_GeneratingParanthesizedFactorsRecursive(string s)
        {
            if(s.Length == 1)
            {
                return new string[] {s};
            }
            if(s.Length == 2)
            {
                string r = "(" + s + ")";
                return new string[] { r };
            }
            List<string> results = new List<string>();
            for (int i = 1; i < s.Length; i++)
            {
                var r1 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                    s.Substring(0, i));
                var r2 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                    s.Substring(i));
                foreach(var s1 in r1)
                {
                    foreach(var s2 in r2)
                    {
                        string r = "(" + s1 + s2 + ")";
                        results.Add(r);
                    }
                }
            }
            return results.ToArray();
        }

All possible balanced parenthesis using Catalan recursive relationship

C_n counts the number of expressions containing n pairs of parentheses which are correctly matched

1, 1, 2, 5, 14, 42, 132, etc...

i.e, c0 = empty (considered one for generalization)

c1 = []

c2 = [[]], [][]

c3 = [[[]]], [[][]], [[]][], [][[]], [][][]

Essentially one need to notice that any correct (balanced) balanced parenthesized strings can be represented with [c']c'' where c' and c'' are valid strings.

i.e, it satisfies Catalan recursive relationship :)

Cn = c0*Cn-1 + C1*Cn-2+....+Cn-2*C1+Cn-1*C0

or in other words,

Cn string = [C0]*Cn-1+[C1]*Cn-2+......+[Cn-2]*C1+[Cn-1]*C0

Below is the corresponding code:

Code Snippet

string[] CatalanNumber_AllPossibleParanthesis(int N)
        {
            Assert.IsTrue(N >= 0);
            if(N==0)
            {
                return new string[] {" "};
            }
            if(N == 1)
            {
                return new string[] { "[]" };
            }
            
            List<string> results = new List<string>();
            for (int i = 0; i <= (N - 1); i++)
            {
                var r1 = this.CatalanNumber_AllPossibleParanthesis(i);
                var r2 = this.CatalanNumber_AllPossibleParanthesis(N - 1 - i);
                
                foreach (var s1 in r1)
                {
                    foreach (var s2 in r2)
                    {
                        //[c']c" - will be of the form
                        string r = "[" + s1.Trim() + "]" + s2.Trim();
                        results.Add(r);
                    }
                }
            }
            return results.ToArray();
        }

Number of full binary trees, binary search trees, binary trees etc.

C_n is the number of full binary trees with n + 1 leaves:

Note: basically only the structure is taken into account, not the data.

Then, one can say C0 = 1 (number of binary trees with '1' leaf)
                              C1 = 1 (number of binary trees with '2' leaves)
                              C3 = C0*C1 (number of binary trees on left with '1' leaf and on right with '2' leaves) + C1*C0 (vice versa)
So, one can define Cn = C0*Cn-1 ('1' leaf on left and 'n' leaves on right) + c1*Cn-2+....+Cn-2*C1 (n-1 leaves on left and 2 on right)+Cn-1*C0 (n leaves on left and 1 leaf on right)

Cn is the total number of binary search trees that can be constructed from given 'N' distinct elements

i.e, C0 = 1 (empty tree)
      C1 = 1 (with one element)
      C2 = 2 (with two elements)
      C3 = C0*C2 (none on left and 2 on right) + C1*C1 (using one element on both sides)+C2*C0

i.e, it satisfies Catalan recursive function, and Cn is nothing but Catalan number.

No. of structurally equivalent binary trees with given 'N' nodes is Cn as well. And by taking the data into consideration, then total number of binary trees are N!*nthCatalanNumber.

Below is the code to generate total number of binary search trees (Catalan Number):

Code Snippet

public int DP_Catalan_TotalBinarySearchTrees(int N)
        {
            if (N == 0)
            {
                return 1;
            }
            if (N == 1)
            {
                return 1;
            }
            int[] DP_Catalan_Cache = new int[N + 1];
            DP_Catalan_Cache[0] = 1;
            DP_Catalan_Cache[1] = 1;
            for(int i = 2;i<=N; i++)
            {
                int sum = 0;
                for(int j=0;j<i;j++)
                {
                    sum += (DP_Catalan_Cache[j]*DP_Catalan_Cache[i-1-j]);
                }
                DP_Catalan_Cache[i] = sum;
            }
            return DP_Catalan_Cache[N];
        }
        public int GetCatalan_TotalBinarySearchTrees(int N)
        {
            if(N==0)
            {
                return 1;
            }
            if(N==1)
            {
                return 1;
            }
            int sum = 0;
            for(int i = 1;i<=N;i++)
            {
                int totalLeftTrees = this.GetCatalan_TotalBinarySearchTrees(i - 1);
                int totalRightTrees = this.GetCatalan_TotalBinarySearchTrees(N - i);
                sum += (totalLeftTrees * totalRightTrees);
            }
            return sum;
        }

Below are the corresponding Unit Tests

Code Snippet

[TestCategory(Constants.Recursion)]
        [TestMethod]
        public void AllPossibleParanthesisTests()
        {
            int[] CatalanNumbers = new int[] { 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 };
            for(int i=1;i<=10;i++)
            {
                var results2 = this.GetAllPossibleParanthesis_2(i);
                Assert.AreEqual(results2.Length, CatalanNumbers[i - 1]);
                var results = this.CatalanNumber_AllPossibleParanthesis(i);
                Assert.AreEqual(results.Length, CatalanNumbers[i - 1]);
                Debug.WriteLine("-----------------------------------------------");
                foreach (string s in results2)
                {
                    Assert.IsTrue(results.Any(rs => rs.Equals(s)));
                }
            }
        }

Code Snippet

 [TestMethod]
        public void CatalanNumber_GeneratingParanthesizedFactorsTests()
        {
            var CatalanNumbers = new int[] { 1, 1, 2, 5, 14, 42, 132, 429, 
                1430, 4862, 16796 };
            string input = "";
            for (int i = 1; i <= 10; i++)
            {
                input += i;
                var results2 = this.CatalanNumber_GeneratingParanthesizedFactors(input);
                Assert.AreEqual(results2.Length, CatalanNumbers[input.Length-1]);
                Debug.WriteLine("-----------------------------------------------");
                foreach (string ss in results2)
                {
                    Debug.WriteLine(ss);
                }
            }
            string s = "a";
            var r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            Assert.AreEqual(r.Length, 1);
            Assert.AreEqual(s, r[0]);
            s = "ab";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            Assert.AreEqual("(ab)", r[0]);
            s = "abc";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            string[] output = new string[] { "(a(bc))", "((ab)c)" };
            Assert.AreEqual(2, r.Length);
            foreach(var o in output)
            {
                Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
            }
            s = "abcd";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            
            output = new string[] { "(a(b(cd)))", "(a((bc)d))", "((ab)(cd))", "(((ab)c)d)", "((a(bc))d)"};
            Assert.AreEqual(5, r.Length);
            foreach (var o in output)
            {
                Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
            }
        }

Code Snippet

[TestMethod]
        public void Catalan_TotalBinarySearchTreesTests()
        {
            var CatalanNumbers = new int[] { 1, 1, 2, 5, 14, 42, 132, 429, 
                1430, 4862, 16796 };
            for(int i =0;i<CatalanNumbers.Length;i++)
            {
                int n = this.GetCatalan_TotalBinarySearchTrees(i);
                Assert.AreEqual(CatalanNumbers[i], n);
                int n1 = this.DP_Catalan_TotalBinarySearchTrees(i);
                Assert.AreEqual(n, n1);
            }
        }

Problem Definition

Given target 't', and a collection of positive integers w1, w2, w3, ..., wn, determine whether there is some selection among the weights so that the total is exactly 't'.

For ex, if t = 10, and the weights are 7, 5, 4, 4, and 1, then the answer is - yes there is selection 5, 4, 1 whose some is '10'

Brute Force

One obvious solution is going through all the subsets of given set of weights, and see if there is any combination that sums up to given total. As we all know set of 'n' elements will have up-to 2^n subsets - which are nothing but no. of combinations. So, the algorithm will be exponential.

Basic gist of the below algorithm is that either item contributes to get to given target 't' or not. So, initially it assumes that the item contributes to get to the given target, and see if rest of the components can contribute to remaining weight. If it is not possible then it checks for the other possibility that the item doesn't contribute to get to the given target, and see if the remaining elements can form the target.

Code Snippet

private bool KnapsackSimplifiedProblemRecursive(int[] weights, int sum, int currentSum, int index, List<int> itemsInTheKnapsack)
        {
            if (currentSum == sum)
            {
                return true;
            }
            if (currentSum > sum)
            {
                return false;
            }
            if (index >= weights.Length)
            {
                return false;
            }
            itemsInTheKnapsack.Add(weights[index]);
            bool flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: currentSum + weights[index],
                index: index + 1, itemsInTheKnapsack: itemsInTheKnapsack);
            if (!flag)
            {
                itemsInTheKnapsack.Remove(weights[index]);
                flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum, index + 1, itemsInTheKnapsack);
            }
            return flag;
        }

Basically above private method will be invoked by the following public method.

Code Snippet

public bool KnapsackRecursive(int[] weights, int sum, out List<int> knapsack)
        {
            if(sum <= 0)
            {
                throw new ArgumentException("sum should be +ve non zero integer");
            }
            knapsack = new List<int>();
            bool fits = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: 0, index: 0, 
                itemsInTheKnapsack: knapsack);
            return fits;
        }

Time Complexity

Another way to prove that above algorithm is exponential is by considering worst case. Assume that the given target cannot be achieved by the given weights. That means, it essentially go through all combinations which is clearly exponential.

Removing tail recursion

Tail recursion means, at the end of the method typically there will be just recursive call. typically these can be removed either with using a stack or goto statements. Below is the version of removing tail recursion using stack:

Code Snippet

public bool SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(int[] weights, int sum, out List<int> knapsack)
        {
            this.Validate(weights, sum);
            var knapsackIndices = new List<int>();
            knapsack = new List<int>();
            Stack<SubsetSum_NoRepetition_KnapsackStackNode> stack = new Stack<SubsetSum_NoRepetition_KnapsackStackNode>();
            stack.Push(new SubsetSum_NoRepetition_KnapsackStackNode() { sumOfWeightsInTheKnapsack = 0, nextItemIndex = 1 });
            stack.Push(new SubsetSum_NoRepetition_KnapsackStackNode() { sumOfWeightsInTheKnapsack = weights[0], nextItemIndex = 1, includesItemAtCurrentIndex = true });
            knapsackIndices.Add(0);
 
            while (stack.Count > 0)
            {
                var top = stack.Peek();
                if (top.sumOfWeightsInTheKnapsack == sum)
                {
                    int count = 0;
                    foreach (var index in knapsackIndices)
                    {
                        var w = weights[index];
                        knapsack.Add(w);
                        count += w;
                    }
                    Debug.Assert(count == sum);
                    return true;
                }
                //basically either of the below three cases, we dont need to traverse/explore adjuscent
                // nodes further
                if ((top.nextItemIndex == weights.Length) //we reached end, no need to traverse
                    || (top.sumOfWeightsInTheKnapsack > sum) // last added node should not be there
                    || (top.alreadyExploredAdjuscentItems)) //already visted
                {
                    if (top.includesItemAtCurrentIndex)
                    {
                        Debug.Assert(knapsackIndices.Contains(top.nextItemIndex - 1));
                        knapsackIndices.Remove(top.nextItemIndex - 1);
                    }
                    stack.Pop();
                    continue;
                }
 
                var node1 = new SubsetSum_NoRepetition_KnapsackStackNode();
                node1.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack;
                node1.nextItemIndex = top.nextItemIndex + 1;
                stack.Push(node1);
 
                var node2 = new SubsetSum_NoRepetition_KnapsackStackNode();
                knapsackIndices.Add(top.nextItemIndex);
                node2.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack + weights[top.nextItemIndex];
                node2.nextItemIndex = top.nextItemIndex + 1;
                node2.includesItemAtCurrentIndex = true;
                stack.Push(node2);
 
                top.alreadyExploredAdjuscentItems = true;
            }
            return false;
        }
        class SubsetSum_NoRepetition_KnapsackStackNode
        {
            public int sumOfWeightsInTheKnapsack;
            public int nextItemIndex;
            public bool alreadyExploredAdjuscentItems;
            public bool includesItemAtCurrentIndex;
        }

Reference(s)

"DataStructures and Algorithms" by Aho, Hopcroft, and Ullman http://www.amazon.com/Data-Structures-Algorithms-Alfred-Aho/dp/0201000237)
http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

Programmer

Labels

Monday, August 4, 2014

Catalan number applications - balanced paranthesis, number of binary search trees etc..