사용하지 않은 조합 찾기

Question

아직 배열에없는 조합을 찾는 빠른 방법은 무엇입니까?

예컨대, 나는 점의 목록이 있습니다 [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

두 배열에서 차이를 얻기 위해 두 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)입니다. (2)를 삽입 connections의 해시 테이블을 사용 -

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

당신이 나올 때까지 바깥 쪽 루프를 반복 할 수 있습니다. 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; }