查找未使用的組合

Question

找到數組中尚未存在的組合的快速方法是什麼？

E.g，我點的名單：[1, 2, 4, 9]

而且我有連接的列表[[1,2], [1,4], [1,9], [2,4], [4,9]]

所以在這個列表中缺少的連接是[2,9]。由於有一個要求：每個整數必須連接到一個更大的整數。

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

您可以使用.reduce方法，以生成兩個elements.Then的所有組合仍將是唯一的事情就是從兩個數組得到的差異。

爲此，您可以使用filter方法，該方法接受callback方法。

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