Longest Common Subsequence

Longest Common Subsequence(counting)

    A. Third Edition

    I actually make a fool of myself by mixing up the permutations with combinations:

    >>What you call "permutation number" is commonly called "binomial
    >>coefficient". And the binomial coefficient (8, 4) is 70.

    What is the largest possible times of calling of LCS(1,1)? It is originally a problem in assignment aiming to

    prove the benefit of dynamic programming against purely recursion. However, the solution is not very convincing.

    B.The problem

The following recursive algorithm computes the length of a

longest common subsequence of sequences

a1a2 . . . am and b1b2 . . . bn.

LCS(

a1a2 . . . am; b1b2 . . . bn):

if

m = 0 or n = 0

then

return 0;

else if

am = bn

then

return 1+ LCS(a1a2 . . . am-1; b1b2 . . . bn-1);

else

return the maximum of

LCS(

a1a2 . . . am; b1b2 . . . bn-1) and LCS(a1a2 . . . am-1; b1b2 . . . bn);

end

end

For each choice of sequences

a1a2 . . . ak and b1b2 . . . bk, a single call of

LCS(

a1a2 . . . ak; b1b2 . . . bk) spawns some number of calls of LCS(a1; b1); let

f

(k) denote the largest of these numbers. What is the largest lower bound

on

f(k) that you can find? Justify your answer (but do not bother justifying

its optimality).

One answer:

C(2k - 2, k - 1); attained, for instance, when ai = 0 for all i and

b

j = 1 for all j.

The explanation is that starting from lower-right-corner, you have total 2(k-1) step to reach the

upper-left-corner. If we use "H" for horizontal step, "V" for vertical step, the total permutation of (k-1)

steps of "H" among total 2(k-1) steps of both "H" and "V" form the recursion. i.e. "HHVHVV" when k=4; But the

problem is that all these sequence will happen within one recursive call? And second question is whether each

of these call will finally call LCS(1,1)?

C.The idea of program
กก

It is the same for me to start from beginning instead from end because it is more convenient to operate from

beginning than from end of string.

The result is quite amazing, at least for me. As I didn't expect the difference is so big. Even the total

repeated recursion number is quite large.

I can even calculate recursion call like "real dynamic programming" by avoiding repeated calls. but I am too

tired after almost four hours since 5:00AM.

    D.The major functions

    กก

    E.Further improvement

    กก

    F.File listing

    1. LCS.cpp

    กก

    file name: LCS.cpp

    #include <stdio.h>
    #include <string.h>
    #include <math.h>

    const int StringLength=5;
    char* leftString="abcde";
    char* rightString="uvwxy";
    int counter=0;
    int totalCounter=0;

    int LCS(char* left, char* right);
    int max(int i, int j);

    int combine(int total, int choice);

    int repeat[StringLength+1][StringLength+1];
    void initialize();

    int factorial(int number);

    void calculate();

    int main()
    {
    	int total, choice;
    	initialize();
    	printf("string1 is:%s, string2:%s\nThe LCS is:%d\n", leftString, rightString,
    		LCS(leftString, rightString));
    	total=2*(strlen(leftString)-1);
    	choice=strlen(leftString)-1;
    	printf("the times called for LCS(1,1) is:%d\n", counter);
    	printf("permutation number (%d, %d) is %d\n", total, choice, combine(total, choice));
    	printf("total counter:%d\n", totalCounter);
    	calculate();
    	return 0;
    }

    void calculate()
    {
    	int result=0;
    	for (int i=0; i<StringLength+1; i++)
    	{
    		for (int j=0; j<StringLength+1; j++)
    		{
    			if (repeat[i][j]>0)
    			{
    				result+=repeat[i][j]-1;
    				printf("repeat[%d][%d]=%d\n", i, j, repeat[i][j]);
    			}
    		}
    	}
    	printf("total repeated times %d\n", result);
    }

    void initialize()
    {
    	for (int i=0; i<StringLength; i++)
    	{
    		for (int j=0; j<StringLength; j++)
    		{
    			repeat[i][j]=0;
    		}
    	}
    }

    int max(int i, int j)
    {
    	return i>j?i:j;
    }

    int factorial(int number)
    {
    	int result=1;
    	for (int i=1; i<=number; i++)
    	{
    		result*=i;
    	}
    	return result;
    }

    int combine(int total, int choice)
    {
    	int result=1;
    	for (int i=total; i>choice; i--)
    	{
    		result*=i;
    	}
    	return result;
    }

    int LCS(char* left, char* right)
    {
    	int row, col;
    	totalCounter++;
    	row=*left=='\0'?0:strlen(left);
    	col=*right=='\0'?0:strlen(right);
    	repeat[row][col]++;
    	if (*left=='\0'||*right=='\0')
    	{
    		return 0;
    	}
    	//printf("string1 is:%s, string2:%s\n", left, right);
    	if (*(left+1)=='\0'&&*(right+1)=='\0')
    	{
    		printf("string1 is:%s, string2:%s\n", left, right);
    		counter++;
    	}
    	if (*left==*right)
    	{
    		return 1+LCS(left+1, right+1);
    	}
    	else
    	{
    		return max(LCS(left+1, right), LCS(left, right+1));
    	}
    }

    How to run?

    The two string are length of 5 and has nothing in common. In order for easy reading, I use character instead of

    0 and 1's.

    string1 is:abcde, string2:uvwxy
    The LCS is:0
    the times called for LCS(1,1) is:70
    permutation number (8, 4) is 1680
    total counter:503
    repeat[0][1]=70
    repeat[0][2]=35
    repeat[0][3]=15
    repeat[0][4]=5
    repeat[0][5]=1
    repeat[1][0]=70
    repeat[1][1]=70
    repeat[1][2]=35
    repeat[1][3]=15
    repeat[1][4]=5
    repeat[1][5]=1
    repeat[2][0]=35
    repeat[2][1]=35
    repeat[2][2]=20
    repeat[2][3]=10
    repeat[2][4]=4
    repeat[2][5]=1
    repeat[3][0]=15
    repeat[3][1]=15
    repeat[3][2]=10
    repeat[3][3]=6
    repeat[3][4]=3
    repeat[3][5]=1
    repeat[4][0]=5
    repeat[4][1]=5
    repeat[4][2]=4
    repeat[4][3]=3
    repeat[4][4]=2
    repeat[4][5]=1
    repeat[5][0]=1
    repeat[5][1]=1
    repeat[5][2]=1
    repeat[5][3]=1
    repeat[5][4]=1
    repeat[5][5]=1
    total repeated times 468
    Press any key to continue