共通要素を含むサブアレイを削除する

Question

タイトルとして、入力が[[1,2]、[3,4]、[1,3]、[5,6]、[6,5]]の場合、出力は[[1,2,3,4]、[5,6]]でなければなりません。 再帰的な部分で間違っています。私のコードでは、それを実行した後、[[1,2,3]、[1,3,4]、[5,6]]を取得します。これは、もう一度マージする必要があることを意味しますが、サブ配列に共通要素が含まれなくなるまでコードを続行します。

は、ここでは、2つのハッシュテーブル、結果setsのための項目の1とそのgroupsとオンを使用することができます私のコード

function need_merge_or_not(arr) 
{ 
    for (var i = 0; i <= arr.length-1; i++) { 
     for (var j = i+1; j <= arr.length-1; j++) { 
     var arr_new = arr[i].concat(arr[j]); 
     //remove deplicates 
     var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos}); 
     if (arr_merge.length < arr_new.length) { 
      return true; 
     } 
     } 
    } 
    return false; 
} 


function merge(arr) 
{ 
    if (arr.length >= 2) { 
    for (var i = 0; i <= arr.length-1; i++) { 
     for (var j = i+1; j <= arr.length-1; j++) { 
     var arr_new = arr[i].concat(arr[j]); 
     var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos}); 
     if (arr_merge.length < arr_new.length) { 
      arr.splice(arr.indexOf(arr[i]), 1); 
      arr.splice(arr.indexOf(arr[j]),1); 
      arr.push(arr_merge); 
     } 
     } 
     if (need_merge_or_not(arr)) { 
      return merge(arr); 
     } 
    } 
    } 
    return arr; 
} 

Answer 1

です。

基本的にアルゴリズムは、プロパティと配列を持つオブジェクトを同じグループに対して生成します。これは、新しい配列を割り当てるときにオブジェクト参照を保持できるためです。

主要な部分は、最初の項目である場合は外側の配列を繰り返して内部の配列をチェックし、存在するかどうかハッシュテーブルをチェックし、存在しない場合はvaluesプロパティを持つ新しいオブジェクトを生成します。空の配列を値として返します。また、項目をキーとしてsetsに実際のオブジェクトを割り当てます。

次のステップでは、ハッシュテーブルが再度チェックされ、存在しなければ、最初の要素のオブジェクトを割り当てます。

一意の値だけを維持するためにチェックが行われ、アイテムが存在しない場合、アイテムはハッシュテーブルのvalues配列にプッシュされます。

次に、最初のアイテムのオブジェクトが実際のアイテムのオブジェクトと等しくないかどうかを調べることによって、配列を結合するパートが続きます。そうであれば、実際のアイテムの値の最初のアイテムからキーをsetsから削除し、実際のアイテムの配列を最初のアイテムのオブジェクトの値に連結します。その後、値オブジェクトは実際のアイテムのオブジェクトに割り当てられます。

その後、setsは、setsオブジェクトを反復して結果セットにマップされ、valuesプロパティは値として取得されます。

var array = [[1, 2], [3, 4], [1, 3], [5, 6], [6, 5]], 
 
    groups = {}, 
 
    sets = {}, 
 
    result; 
 
    
 
array.forEach(function (a) { 
 
    a.forEach(function (b, i, bb) { 
 
     if (i === 0 && !groups[b]) { 
 
      groups[b] = { values: [] }; 
 
      sets[b] = groups[b]; 
 
     } 
 
     if (!groups[b]) { 
 
      groups[b] = groups[bb[0]]; 
 
     } 
 
     if (groups[b].values.indexOf(b) === -1) { 
 
      groups[b].values.push(b); 
 
     } 
 
     if (groups[bb[0]] !== groups[b]) { 
 
      delete sets[groups[b].values[0]]; 
 
      groups[bb[0]].values = groups[bb[0]].values.concat(groups[b].values); 
 
      groups[b].values = groups[bb[0]].values;      
 
     } 
 
    });  
 
}); 
 

 
result = Object.keys(sets).map(function (k) { 
 
    return sets[k].values; 
 
}); 
 

 
console.log(result);

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

Answer 2

私はそれを考え出しました。コードは次のとおりです。

function merge(arr){ 
    var input = []; 
    for(var i = 0; i < arr.length; i++){ 
    input.push(arr[i]); 
    } 
    if (arr.length >= 2) { 
    for (var i = 0; i < arr.length; i++) { 
     for (var j = i+1; j < arr.length; j++) { 
     var arr_new = arr[i].concat(arr[j]); 
     //remove duplicates 
     var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos}); 
     if (arr_merge.length < arr_new.length) { 
      arr.splice(arr.indexOf(arr[i]), 1, arr_merge); 
      arr.splice(arr.indexOf(arr[j]),1); 
      j--; 
     } 
     } 
    } 
    if (!arraysEqual(input, arr)) {merge(arr)}; 
    } 
    return arr; 
    //Input:[[1,2], [3,4], [1,3], [5,6], [6,5]] 
    //Output:[[1,2,3,4], [5,6]] 
} 

function arraysEqual(a, b) { 
    if (a === b) return true; 
    if (a == null || b == null) return false; 
    if (a.length != b.length) return false; 

    for (var i = 0; i < a.length; ++i) { 
    if (a[i] !== b[i]) return false; 
    } 
    return true; 
}