配列の配列内のすべての重複したサブセットを見つけて抽出する方法は？

Question

私は2つのサブセット7,8及び1 2倍含まれ、この配列があります。

[ 
    [1,2], 
    [9,10,7,8], 
    [5,6,7,8], 
    [1] 
] 

私が見つけて、すべてのサブセット（一回以上含まれている、自分以外のIE）を抽出することができますどのようにこの配列の内側と結果は？

[ 
    [2], 
    [9,10], 
    [7,8], 
    [5,6], 
    [1] 
] 

サブセットは常に連続しています。つまり、9,7は9,10,7,8のサブセットと見なすべきではありません。

EDIT：それは問題ではないが、アイテムが起動アレイのようでなければならない最終的なアレイの 順序：

ok=[    ok=[   notOk=[ 
     [2],    [9,10],   [10,9], 
     [9,10],   [2],    [2], 
     [7,8],    [5,6],    [6,5], 
     [5,6],    [1],    [1], 
     [1]    [7,8]    [8,7] 
    ]     ]     ] 

任意の非再帰的な解決策は、非常に高く評価されるだろう。

Answer 1

私はそれを発生アレイを提供する各個別の値のマップを（ハッシュ）、ビルドこのソリューションを提案します。このような各配列要素は、値が発生するサブ配列（入力から）と、そのサブ配列内のインデックスを提供します。

第2のステップでは、等しい値の要素の後続を比較します。これらの値もすべて同じであり、その値が他の場所（すなわち、異なる先行値）で発生していない場合、後続値は前の値と結合されたままでなければならないと結論づけられる。これが起こると、次の後継者がテストされ、おそらく破られていない三つ子が形成されるかどうかが見えます。

以下のコードでは、このソリューションでは他のソリューション（私の前に投稿）が生成するものと比較して、このソリューションが異なる出力を生成するため、質問に示されたものとは異なる入力データを使用しています。

コードがES6の構文を使用します。

var input = [ 
 
    [1,3], 
 
    [9,11,7,12,2], 
 
    [5,0,7,12,2,8,10,7,12,2], 
 
    [1] 
 
]; 
 

 
// build hash (map) 
 
var hash = input.reduce ((hash, arr) => 
 
    arr.reduce ((hash, val, index) => 
 
     // Collect the array element's references in a Map keyed by value: 
 
     hash.set(val, (hash.get(val) || []).concat({ arr, index })), 
 
     hash 
 
    ), new Map() // initial value of the hash is an empty Map 
 
); 
 

 
var result = Array.from(hash, ([val, matches]) => { 
 
    var match = matches[0]; 
 
    // Compare the sucessors of the elements that are equal 
 
    for (var offset = 1; match.index + offset < match.arr.length; offset++) { 
 
     var valAtOffset = match.arr[match.index+offset]; 
 
     // If the sucessor values only occur as successor of the preceding value, 
 
     // and all these successors have the same value, then keep this value together 
 
     // with the preceding value: 
 
     if (hash.get(valAtOffset).length !== matches.length || 
 
      matches.some(match => match.arr[match.index+offset] !== valAtOffset)) break; 
 
     // Remove the hash entry for the value that is now part of this unbroken sequence 
 
     hash.delete(valAtOffset); 
 
    } 
 
    return match.arr.slice(match.index, match.index+offset); 
 
}); 
 

 
// output: 
 
console.log(JSON.stringify(result));

Answer 2

共通項目にマップを使用できます。 1回のカウントでアイテムをマップから削除し、最初に共通の結果セットを構築するためにマップを使用します。次に、結果セットに残りのものを使用し、共通かどうかを確認した後、戻り値をチェックするか、最後に結果セットに追加するか、結果セットに新しい配列を追加します。

var data = [[1, 2], [9, 10, 7, 8], [5, 6, 7, 8], [1]], 
 
    result = [], 
 
    common = new Map; 
 

 
// get all items and store the occurence 
 
data.forEach((a, i) => a.forEach(b => { 
 
    if (!common.has(b)) { 
 
     common.set(b, []); 
 
    } 
 
    common.get(b).push(i); 
 
})); 
 

 
// keep only occurence of more then one 
 
common.forEach((v, k, m) => v.length === 1 && m.delete(k)); 
 

 
// get common keys, sort and push single or contiguous elements to the result set 
 
[...common.keys()].sort((a, b) => a - b).forEach((k, i, kk) => { 
 
    var l = kk[i - 1]; 
 
    if (l === k - 1 && common.get(l).toString() === common.get(k).toString()) { 
 
     result[result.length - 1].push(k); 
 
     return; 
 
    } 
 
    result.push([k]); 
 
}); 
 

 
// push non common items to the result set 
 
data.forEach((a, i) => a.forEach(function (b, i, bb) { 
 
    var l = bb[i - 1]; 
 
    if (common.has(b)) { 
 
     return; 
 
    } 
 
    if (!common.has(l) && l === b - 1) { 
 
     result[result.length - 1].push(b); 
 
     return; 
 
    } 
 
    result.push([b]); 
 
})); 
 

 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }