2

バケットにグループ化されている、重複しない可能性のあるすべてのアイテムの組み合わせを見つける必要があります。バケットはいくつあってもかまいませんし、各バケットにはいくつものアイテムを含めることができます。有効な組み合わせには、各バケットから正確に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で実装しています。

4

1 に答える 1

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（args）のデカルト積に対する_.first（args）の平坦化された展開を計算する再帰呼び出しに変換することにより、フィルターを任意の数の間隔に一般化できます。

可能なすべてのペアを生成し、を呼び出すことにより、フィルターを任意の数の間隔に一般化できます!_.any(pairs, function(pair) { return overlaps.prototype.apply(undefined, pair); });。

于 2013-02-08T02:31:01.330 に答える