サブシーケンスからスーパーシーケンスを見つけるための多数決マージアルゴリズムの実装？

Question

私は、各値の相対的な順序が可能な限り維持される単一のスーパーシーケンスに結合したい、独自の値の一連の小さなセットを持っています。例えば（簡略化のために無視文字列の前後に引用符）：

list1 = [Mary, Bob, Sue, Roger] 
list2 = [Bob, Alice, Sue, Dave] 
list3 = [Mary, Bob, Larry, Sue, Roger] 

superSequence = [Mary, Bob, Alice, Larry, Sue, Roger, Dave] 

目標は、元のリストのような、再現可能なオブジェクトを生成することである。

しばらくそのオブジェクトを無視

obj = { 
    Mary: [1, 3], 
    Bob: [1, 3], 
    Alice: [2], 
    Larry: [3], 
    Sue: [1, 2, 3], 
    Roger: [1, 3], 
    Dave: [2] 
} 

をキーの順序はすべての場合で保証されているわけではありません。これらのキーを反復し、関連する各配列のインデックスを使用して元のリストを再生成することができます。スーパーシーケンスはJSオブジェクトとして表されるため、スーパーシーケンスは一意でなければなりません。

明らかに、シーケンスのすべてのセットは、このように組み合わせることができません。

list1 = [Mary, Bob, Sue] 
list2 = [Bob, Mary, Sue] 

superSequence = [Mary, Bob, Sue] OR 
superSequence = [Bob, Mary, Sue] 

は1をピッキングや他の注文があった場所強調表示することができ、アルゴリズムのためのボーナスポイントと、ほとんどの場合、問題ないはずです不確定。

これを研究するにあたって、圧縮、バイオインフォマティクスなどの分野で十分に研究されているNP困難な問題に遭遇したようです。この問題の合理的にまともな近似と思われる多数決アルゴリズムと呼ばれるものがありますが、学術論文pseudo-codeを使用可能なものに翻訳する私の能力は、長年にわたって萎縮しています。だから私は、JSやCやPythonやマジックライブラリに依存しないもので実際の実装を見つけることを望んでいました。

Answer 1

あなたの質問にはもっと簡単な答えがあることに気付きました。私たちは、同じ名前が与えられたリスト内に複数回発生していないと仮定することができますので、これは動作します：それは、同じ名前を複数回含むことがリストのための、より正確であるため、

var simpleCombine = function (arr1, arr2) { 
    "use strict"; 
    arr1 = JSON.parse(JSON.stringify(arr1)); 
    arr2 = JSON.parse(JSON.stringify(arr2)); 
    var i, j, arrOut = []; 
    while (arr1.length) { 
     var val = arr1.shift(), found = false; 
     for (j = 0; j < arr2.length; j += 1) { 
      if (val === arr2[j]) { 
       //If we wound an overlap then put everything to the left of it 
       // in arr2 into the final array 
       found = true; 
       var pos = arrOut.length; 
       arrOut.push(val); 
       var newVals = arr2.splice(0, j); 
       while (newVals.length) { 
        arrOut.splice(pos, 0, newVals.pop()); 
       } 
       arr2.shift(); //get rid of dup 
       break; 
      } 
     } 
     if (!found) { 
      //No overlap found, just add it to the out array 
      arrOut.push(val); 
     } 
    } 
    //anything left in arr2? Add it to out array 
    arrOut = arrOut.concat(arr2); 

    //check for duplicates based on user requirement of each item in the 
    // sequence only occurs once. 

    for (i = 0; i < arrOut.length; i += 1) { 
     for (j = i + 1; j < arrOut.length; j += 1) { 
      if (arrOut[i] === arrOut[j]) { 
       //If we find an overlap warn the user, and remove the dup. 
       console.warn('Even with strict ordering, multiple solutions are possible'); 
       arrOut.splice(i,1); 
       i -= 1; 
       break; 
      } 
     } 
    } 

    return arrOut; 
}; 

var findMultipleSCS = function (arr) { 
    var first = arr.shift(); 
    while (arr.length) { 
     first = simpleCombine(first, arr.shift()); 
    } 
    return first; 
}; 

list1 = ["Mary", "Bob", "Sue", "Roger"]; 
list2 = ["Bob", "Alice", "Sue", "Dave"]; 
list3 = ["Mary", "Bob", "Larry", "Sue", "Roger"]; 

console.log(findMultipleSCS([list1, list2, list3])); 

私のオリジナルの答えは以下の通りです。

//This code works for things where the important thing is that order is 
//maintained, not that each entry only occurs once 
var findSCS = (function() { 
    'use strict'; 
    var lcsLen, lcsBack, combine; 
    lcsLen = function(arr1, arr2) { 
     //This function moves through the arrays developing the 
     // length of the longest possible sequence of identical order. 
     var dists = [[0]], i, j; 
     for (i = 0; i < arr1.length; i += 1) { 
      dists[i + 1] = []; 
      for (j = 0; j < arr2.length; j += 1) { 
       dists[i + 1][0] = 0; // initialize 0'th column/row with 0 
       dists[0][j + 1] = 0; // this could be done in a separate loop 
       dists[i + 1][j + 1] = dists[i + 1][j + 1] || 0; // initialize i,j 
       if (arr1[i] === arr2[j]) { 
        //if this condition is met then we have a longer overlap 
        dists[i + 1][j + 1] = dists[i][j] + 1; 
       } else { 
        //if not take the max length so far 
        dists[i + 1][j + 1] = Math.max(dists[i][j + 1], dists[i + 1][j]); 
       } 
      } 
     } 
     return dists; 
    }; 

    lcsBack = function (dists, x, y, i, j) { 
     //this recursive function takes the longest possible array and build 
     // the actual list starting from the bottom right of the matrix 
     // created by lcsLen 
     if (!i || !j) { 
      return []; 
     } else if(x[i - 1] === y[j - 1]) { 
      return lcsBack(dists, x, y, i - 1, j - 1).concat([x[i - 1]]); 
     } else { 
      if (dists[i][j-1] > dists[i-1][j]) { 
       return lcsBack(dists, x, y, i, j-1); 
      } else { 
       return lcsBack(dists,x,y,i-1,j); 
      } 
     } 
    }; 

    combine = function (lcs, arr1, arr2) { 
     //this take the lcs and fills in the non-overlapping part of 
     // the original lists, creating the scs 
     var out = JSON.parse(JSON.stringify(arr1)); 
     var i, testing = 0, outPos = 0, positions = [0]; 
     for (i = 0; i < arr1.length && testing < lcs.length; i += 1) { 
      if (lcs[testing] === arr1[i]) { 
       positions[testing + 1] = i; 
       testing += 1; 
      } 
     } 
     testing = 0; outPos = 0; 
     for (i = 0; i < arr2.length; i += 1) { 
      if (lcs[testing] === undefined || lcs[testing] !== arr2[i]) { 
       out.splice(positions[testing] + outPos, 0, arr2[i]); 
       outPos += 1; 
      } else { 
       testing += 1; 
       outPos += 1; 
      } 
     } 

     return out; 
    }; 

    return function (arr1, arr2) { 
     //get the length matrix to determine the maximum sequence overlap 
     var lcsLenMat = lcsLen(arr1,arr2); 
     //Take that distance matrix and build the actual sequence (recursively) 
     var lcs = lcsBack(lcsLenMat, arr1, arr2, arr1.length, arr2.length); 
     //Build the SCS 
     var tempScs = combine(lcs, arr1, arr2); 
     //This code will allow for duplicates, and in your second example 
     // It will generate a list with two bobs, which is arguably more 
     // correct for general purpose use. 
     return tempScs; 
}()); 

var findMultipleSCS = function (arr) { 
    var first = arr.shift(); 
    while (arr.length) { 
     first = findSCS(first, arr.shift()); 
    } 
    return first; 
}; 

list1 = ["Mary", "Bob", "Sue", "Roger"]; 
list2 = ["Bob", "Alice", "Sue", "Dave"]; 
list3 = ["Mary", "Bob", "Larry", "Sue", "Roger"]; 

console.log(findMultipleSCS([list1, list2, list3])); 

https://en.wikipedia.org/wiki/Longest_common_subsequence_problemと​​

あなたが得るユニークな非どのソリューションを決定しますこれらを入れる順序から取られたこれらのアイデアのほとんどは。

["Mary", "Bob", "Larry", "Alice", "Sue", "Dave", "Roger"] 

あなたはリスト1、リスト2よりも優先順位を維持したい場合は、LIST3はありませんが、独自のを持っている：インスタンスのリスト1、リスト2の場合は、LIST3はあなたの最初の答えを与える、しかしリスト2は、LIST3は、リスト1はあなたにも、正しいを与えますそれは重複を探してconsole.warnで重複している可能性を警告します。

Answer 2

adussのsimpleCombine()の機能上に構築すると、私はかなりうまくいくと思われる解決策を考え出しました。現在、結果の重複した項目が削除されていることを示すフラグはありませんが、最後のfilter()呼び出しで追加のロジックを使用して実装できます。

function combineLists(...lists) 
 
{ 
 
    var superSequence = lists.slice(1).reduce((list1, list2) => { 
 
     var result = []; 
 

 
      // we need to make a copy of list2 since we mutate it in the loop below 
 
     list2 = [].concat(list2); 
 

 
     list1.forEach(item => { 
 
      var overlapIndex = list2.indexOf(item); 
 

 
      if (overlapIndex > -1) { 
 
        // add 1 to overlapIndex so we also splice out the matching item 
 
       result = result.concat(list2.splice(0, overlapIndex + 1)); 
 
      } else { 
 
       result.push(item); 
 
      } 
 
     }); 
 

 
      // anything remaining in list2 is by definition not in list1, so add 
 
      // those items to the result 
 
     return result.concat(list2); 
 
    }, lists[0]); 
 

 
     // look back at the list up to the current item and then filter it out if 
 
     // there's a duplicate found. this keeps the first instance of each item. 
 
    return superSequence.filter((item, i, list) => list.slice(0, i).indexOf(item) == -1); 
 
} 
 

 
var list1 = ["Mary", "Bob", "Sue", "Roger"], 
 
    list2 = ["Bob", "Alice", "Jimmy", "Chuck", "Sue", "Dave"], 
 
    list3 = ["Mary", "Bob", "Larry", "Sue", "Roger"]; 
 

 
console.log(combineLists(list1, list2, list3).join(" "));