如何找到所有不重叠的组合？
如何找到所有不重叠的组合？
提问于 2013-02-08 09:13:32
我需要找到所有可能的非重叠的项目组合，这些项目被分组到桶中。可以有任意数量的存储桶，并且每个存储桶可以包含任意数量的项。一个有效的组合将恰好包含每个存储桶中的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中实现了这一点。
回答 1
Stack Overflow用户
发布于 2013-02-08 10:31:01
暴力方法是生成桶的笛卡尔乘积，并过滤掉任何无效的桶。因此，假设您的存储桶是简单的项目列表，如下所示：
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)的笛卡尔乘积(Args)上的_.first(args)的展平扩展，从而将过滤器推广到任意数量的间隔。
您可以通过生成所有可能的对并调用!_.any(pairs, function(pair) { return overlaps.prototype.apply(undefined, pair); });，将过滤器概括为任意数量的间隔。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14764160
复制相关文章
相似问题
腾讯云开发者
