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

bj = 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










                                                               
                      







                       back.gif (341 bytes)       

up.gif (335 bytes)                                       
next.gif (337 bytes)