Return to Question

// 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])));

// 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]))); 

JavaScript code:

// 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;
}

Does the algorithm look correct, and did I miss any optimization?

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]))); 

// 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 and i2 are the starting indices in list1 and list2
 function find (i1, i2) {
 let currentVal = list1[i1];
 let ignore = new Set ([currentVal]);
 let maxLength = 1;
 let maxSequence = [currentVal];
 ++ i1;
 // Iterate through list1, stopping when we don't have enough remaining elements
 // to improve on the longest sequence found so far while (i1 < list1.length && (list1.length-i1) > maxLength) {
 // 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, indexList2[list1[i1]]);
 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 (0, indexList2[list1[0]]).maxSequence;
}

// 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;
}