未使用の組み合わせを見つける

Question

まだ配列に存在しない組み合わせを見つけるにはどうすればよいでしょうか？

例えば、私は点のリストがあります：[1, 2, 4, 9]

をそして私はこのリストの不足している接続が[2,9]で接続[[1,2], [1,4], [1,9], [2,4], [4,9]]

のリストを持っています。 1つの要件として：すべての整数はより大きな整数に接続する必要があります。

var points = [1, 2, 4, 9]; 
var connections = [[1,2], [1,4], [1,9], [2,4], [4,9]]; 

var missing = []; 
for(i = 0; i < points.length; i++){ 
    for(j = i + 1; j < points.length; j++){ 
    var found = false; 
    for(var a = 0; a < connections.length; a++){ 
     if(connections[a][0] == points[i] && connections[a][1] == points[j]){ 
     found = true; 
     break; 
     } 
    } 
    if(!found) missing.push([points[i], points[j]]); 
    } 
} 

console.log(missing); 

上記のコードは機能しますが、forループの量は私にはかなり遅いと思います。これを行うより速い方法がありますか？表示をjsfiddle

Answer 1

あなたは残る唯一のことは、二つの配列からの差異を取得することです2 elements.Thenのすべての組み合わせを生成するために、.reduce方法を使用することができます。

このため、callbackメソッドを受け入れるfilterメソッドを使用できます。

var points = [1, 2, 4, 9]; 
 
points=points.sort(); 
 
var connections = [[1,2], [1,4], [1,9], [2,4], [4,9]]; 
 
var combinations = points.reduce(function(arr,elem,i){ 
 
     for(j=i+1;j<points.length;j++) 
 
     arr.push([elem,points[j]]); 
 
     return arr; 
 
},[]); 
 
var diff=combinations.filter(function(elem,i){ 
 
    return connections.find(a=>a[0]==elem[0] && a[1]==elem[1])==undefined; 
 
}); 
 
console.log(diff);

Answer 2

並べ替えることで、2つのネストで行うことができます。ソートにはO（n log n）が必要であり、ループは基本的にO（n^2）です。

var points = [1, 2, 4, 9]; 
var connections = [ 
    [1, 2], 
    [1, 4], 
    [1, 9], 
    [2, 4], 
    [4, 9] 
]; 

connections.sort(); 

var missing = []; 
var currentIndex = 0; 
for (var i = 0; i < points.length; i++) { 
    for (var j = i + 1; j < points.length; j++) { 
    if (connections[currentIndex][0] == points[i] && connections[currentIndex][1] == points[j]) { 
     currentIndex++; 
    } else { 
     missing.push([points[i], points[j]]); 
    } 
    } 
} 

console.log(missing); 

Answer 3

あなたは長さまでだけ外側のループを繰り返すことができ - 2と挿入connectionsのハッシュテーブルを使用します。 connectionsのソート順は関係ありません。

var points = [1, 2, 4, 9], 
 
    connections = [[1, 2], [1, 4], [1, 9], [2, 4], [4, 9]], 
 
    missing = [], 
 
    i, j, 
 
    pair, 
 
    connected = Object.create(null); 
 

 
connections.forEach(function (a) { 
 
    connected[a.join()] = true; 
 
}); 
 

 
for (i = 0; i < points.length - 1; i++) { 
 
    for (j = i + 1; j < points.length; j++) { 
 
     pair = [points[i], points[j]]; 
 
     connected[pair.join()] || missing.push(pair); 
 
    } 
 
} 
 

 
console.log(missing);

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