CODEWITHSUNDEEP
javarecursioninfinitelcs
Ares
Ares

Reputation: 1461

Longest Common Subseqence

I'm trying to write a recursive algorithm that finds the longest common subsequence of two lists, as described in http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined

It appears that the recursion never ends and I cannot figure out what I'm doing wrond

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2) {
    return getLongestSequence(list1, list2, list1.size(), list2.size());
}

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2, int list1index, int list2index) {

    if (list1index == 0 || list2index == 0) {
        return new ArrayList<ActionType>();
    }

    if (list1.get(list1index-1).equals(list2.get(list2index-1))) {
        List<ActionType> retVal = getLongestSequence(list1, list2, list1index-1, list2index-1);
        retVal.add(list1.get(list1index-1));
        return retVal;
    } else {
        List<ActionType> ret1 = getLongestSequence(list1, list2, list1index, list2index-1);
        List<ActionType> ret2 = getLongestSequence(list1, list2, list1index-1, list2index);

        if (ret1.size() > ret2.size()) {
            return ret1;
        } else {
            return ret2;
        }
    }
}

Any help figuring this out is appreciated. Thank you.

Upvotes: 1

Views: 200

Answers (1)

Ares
Ares

Reputation: 1461

The issue was one of complexity. Implementing memorizing reduced the runtime from more than a day to several seconds.

Here is the updated algorithm:

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2) {
    lcsMemorize = new HashMap<Integer, List<ActionType>>();
    return getLongestSequence(list1, list2, list1.size(), list2.size());
}

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2, int list1index, int list2index) {

    List<ActionType> retVal = lcsMemorize.get(list1index + list2index * 1000000);

    if (retVal != null) {
        return retVal;
    } else if (list1index == 0 || list2index == 0) {
        retVal = new ArrayList<ActionType>();
    } else if (list1.get(list1index-1).equals(list2.get(list2index-1))) {
        List<ActionType> returned = getLongestSequence(list1, list2, list1index-1, list2index-1);

        retVal = new ArrayList<ActionType>(returned);
        retVal.add(list1.get(list1index-1));
    } else {
        List<ActionType> ret1 = getLongestSequence(list1, list2, list1index, list2index-1);
        List<ActionType> ret2 = getLongestSequence(list1, list2, list1index-1, list2index);

        if (ret1.size() > ret2.size()) {
            retVal = ret1;
        } else {
            retVal = ret2;
        }
    }

    lcsMemorize.put(list1index + list2index * 1000000, retVal);

    return retVal;
}

Notes:

In my runs, the original lists are 1100 - 1300 elements long and ActionType is an enum. This approach uses a lot of memory. I've had to increase the JVM heap size to 4GB.

Upvotes: 1

Related Questions