겹치지 않는 모든 조합은 어떻게 찾습니까?

Question

버킷으로 그룹화 된 항목의 중첩되지 않는 조합을 모두 찾아야합니다. 여러 개의 버킷이있을 수 있으며 각 버킷에는 여러 개의 항목이 포함될 수 있습니다. 올바른 조합에는 각 버킷의 정확히 1 개의 항목이 포함됩니다.

bucket item start end 
======================== 

     |-- I1  1 5 
B1----|-- I2  6 9 
     |-- I3 15 20 


     |-- I4 6  9 
B2----|-- I5 10 14 
     |-- I6 14 25 


     |-- I7 1  14 
B3----|-- I8 26 40 
     |-- I9 1  20 
     |-- In ... 

Bn ... 

예를 들어, 1,4,8; 1,5,8; 1,6,8; 2,5,8; 2,6,8; 3,4,8; 및 3,5,8.

항목 9는 버킷 1의 모든 항목과 겹치기 때문에 조합으로 나타나지 않으며 옵션이없는 것을 볼 수 있습니다.

이 문제를 어떻게 효율적으로 가장 잘 해결할 수 있습니까? JavaScript JavaScript에서 이것을 구현하고 있습니다.

Answer 1

무차별 방식은 버킷의 데카르트 곱을 생성하고 유효하지 않은 것을 필터링하는 것입니다.

var cp = _.flatten(_.flatten(_.map(B1, function(item1) { 
    return _.map(B2, function(item2) { 
     return _.map(B3, function(item3) { 
      return [item1, item2, item3]; 
     }); 
    }); 
}), true), true); 

당신에게 3 양동이의 직교 제품을 제공합니다 : 그래서, 가정 당신의 버킷은 단순히 항목의 목록의 라인을 따라 뭔가입니다.

_.filter(cp, function(tuple) { 
    return !overlaps(item1, item2) && !overlaps(item1, item3) && !(overlaps(item2, item3); 
}); 

은 원하지 않는 필터를 걸러 낼 것입니다 (적절한 중첩 정의가 있음).

function overlaps(a, b) { 
    return a.lower > b.upper || b.lower > a.upper; 
} 

넌 _.rest (인수)의 직교 제품 위로 _.first (인수)의 평탄화 팽창 산출 재귀 호출 직교 변환하여 제품 간격 임의의 수의 필터를 일반화 할 수있다.

모든 가능한 쌍을 생성하고 !_.any(pairs, function(pair) { return overlaps.prototype.apply(undefined, pair); });을 호출하여 원하는 간격으로 필터를 일반화 할 수 있습니다.