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

您可以通过将笛卡尔积转换为递归调用来将过滤器推广到任意数量的区间，从而计算 _.first(args) 在 _.rest(args) 的笛卡尔积上的展平展开。

您可以通过生成所有可能的对来将过滤器推广到任意数量的间隔，然后调用!_.any(pairs, function(pair) { return overlaps.prototype.apply(undefined, pair); });.

于 2013-02-08T02:31:01.330 回答