In short, the algorithm must find the longest sequence that joins together common sequences from two lists (a more formal specification is given in the code's header).
The lists are assumed to contain the same elements without duplicates.
Example: from [1,2,3,4,5,6] and [1,4,5,2,6,3] the algorithm should return [1,4,5,6].
Does the algorithm look correct, and did I miss any optimization?
// Find the longest sequence seq such that :
// for all i, there exists j and k such that seq[i]=list1[j]=list2[k]
// and seq[i+1]=list1[j']=list2[k'] where j < j' and k < k'.
//
// Precondition : list1 and list2 contain the same elements without duplicates.
//
function findMaxCommonSequence(list1, list2) {
let indexList2 = {}; // Provides O(1) access to the indice in list2 for a given element
list2.forEach ((elt, i) => indexList2[elt] = i);
// i1 is the starting indices in list1
function find (i1) {
let currentVal = list1[i1];
let prefix = [currentVal];
let ignore = new Set (prefix);
let maxLength = 1;
let maxSequence = prefix;
let i2 = indexList2[currentVal]; // i2 is the starting indices in list2
// Iterate through list1, stopping when we don't have enough remaining elements
// to improve on the longest sequence found so far (subsumes the boundary check)
while (list1.length-i1 > maxLength) {
++ i1;
// Only consider the elements that are further into list2
// and are not part of an already explored solution
if (indexList2[list1[i1]] > i2 && !ignore.has (list1[i1])) {
let rec = find (i1);
let sequence = prefix.concat (rec.maxSequence);
ignore = new Set ([...ignore, ...rec.ignore]);
if (sequence.length > maxLength) {
maxLength = sequence.length;
maxSequence = sequence;
}
}
}
return {
maxSequence: maxSequence,
ignore: ignore,
};
}
// Outer loop on the same principle as find() except we don't have a prefix
let i1 = 0;
let ignore = new Set ();
let maxLength = 0;
let maxSequence = [];
while (list1.length-i1 > maxLength) {
if (!ignore.has (list1[i1])) {
let rec = find (i1);
let sequence = rec.maxSequence;
ignore = new Set ([...ignore, ...rec.ignore]);
if (sequence.length > maxLength) {
maxLength = sequence.length;
maxSequence = sequence;
}
}
++ i1;
}
return maxSequence;
}
console.log("[1,2,3,4,5,6] + [1,4,5,2,6,3] -> [1,4,5,6] returns ",
JSON.stringify(findMaxCommonSequence([1,2,3,4,5,6], [1,4,5,2,6,3])));
console.log("[1,4,5,2,6,3] + [1,2,3,4,5,6] -> [1,4,5,6] returns ",
JSON.stringify(findMaxCommonSequence([1,4,5,2,6,3], [1,2,3,4,5,6])));
console.log("[1,4,5,2,6,3] + [1] -> [1] returns ",
JSON.stringify(findMaxCommonSequence([1,4,5,2,6,3], [1])));
console.log("[1] + [1,4,5,2,6,3] -> [1] returns ",
JSON.stringify(findMaxCommonSequence([1], [1,4,5,2,6,3])));
console.log("Using version 2:");
function findMaxCommonSequence2 (list1, list2) {
let indexList2 = {}; // Provides O(1) access to the indice in list2 for a given element
list2.forEach ((elt, i) => indexList2[elt] = i);
function find (list1, i2) {
let ignore = new Set ();
let maxLength = 0;
let maxSequence = [];
let i1 = 0;
while (list1.length-i1 > maxLength) {
let currentVal = list1[i1];
if (indexList2[currentVal] >= i2 && !ignore.has (currentVal)) {
ignore.add (currentVal);
let rec = find (list1.slice (i1+1), indexList2[currentVal]);
let sequence = [currentVal].concat (rec.maxSequence);
ignore = new Set ([...ignore, ...rec.ignore]);
if (sequence.length > maxLength) {
maxLength = sequence.length;
maxSequence = sequence;
}
}
++ i1;
}
return {
maxSequence: maxSequence,
ignore: ignore,
};
}
return find (list1, 0).maxSequence;
}
console.log("[1,2,3,4,5,6] + [1,4,5,2,6,3] -> [1,4,5,6] returns ",
JSON.stringify(findMaxCommonSequence2([1,2,3,4,5,6], [1,4,5,2,6,3])));
console.log("[1,4,5,2,6,3] + [1,2,3,4,5,6] -> [1,4,5,6] returns ",
JSON.stringify(findMaxCommonSequence2([1,4,5,2,6,3], [1,2,3,4,5,6])));
console.log("[1,4,5,2,6,3] + [1] -> [1] returns ",
JSON.stringify(findMaxCommonSequence2([1,4,5,2,6,3], [1])));
console.log("[1] + [1,4,5,2,6,3] -> [1] returns ",
JSON.stringify(findMaxCommonSequence2([1], [1,4,5,2,6,3])));