区间关系组合的生成算法
区间关系组合的生成算法
提问于 2019-05-20 16:42:04
我想生成一些样本数据来处理不同类型的间隔，并希望确保表示所有可能的间隔关系。
对于我来说，{meets，overlaps，is-finished by}是等价的，equals可以忽略，{B starts，A contains }也是等价的。我还将假设所有的间隔都被排序和标记，使得A在B之前开始，B在C之前开始等等。因此，我基本上对三种情况感兴趣：
B之前的
- A (如A=1,2、B=3,4)
- A包含B(如A=1,4、B=2,3)
- A与B重叠(如A=1,3、B=2,4)
引入第三个间隔会产生更多的情况：
- A在B之前，B在C之前(例如A=1,2，B=3,4，C=5,6)
- A在B之前，B包含C(例如A=1,2，B=3,6，C=4,5)
- A在B之前，B与C重叠(例如A=1,2，B=3,5，C=4，5
尽管在A在B之前的情况下，A总是在C之前，但对于我们也需要考虑A和C的关系的其他变体来说，情况并非如此：
- A包含B，B与C重叠，A与C重叠(例如A=1,5，B=2,4，C=3,6)
- A包含B，B与C重叠，A包含C(例如A=1,6，B=2,4，C=3,5)
对于给定的区间数，可能存在多少种不同的关系组合？
生成这些组合的算法是什么？
例如，对于两个间隔的情况，算法可能会产生以下输出来求解：
combination, interval name, start, end
1, A, 1, 2
1, B, 3, 4
2, A, 1, 4
2, B, 2, 3
3, A, 1, 3
3, B, 2, 4编辑:根据MBo的回答，添加了四个区间的解决方案可视化。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-05-20 17:56:33
N个区间有(2*n-1)!！(奇数为double factorial)组合，序列为1,3,15,105,945...
快速实现Python以显示结果。在每个阶段，我们可以开始新的间隔(比前一个开始大1)或完成任何打开的间隔
t = 0
def genintervals(n, level, opstart, opened, s):
if level == 2 * n:
print(s)
global t
t += 1
return
if opstart < n:
genintervals(n, level + 1, opstart + 1, opened + [opstart], s + 's' + str(opstart) + " ")
for i in range(len(opened)):
genintervals(n, level + 1, opstart, opened[0:i] + opened[i+1:], s + 'e' + str(opened[i]) + " ")
s0 s1 s2 e0 e1 e2
s0 s1 s2 e0 e2 e1
s0 s1 s2 e1 e0 e2
s0 s1 s2 e1 e2 e0
s0 s1 s2 e2 e0 e1
s0 s1 s2 e2 e1 e0 //A covers B and C, B covers C
s0 s1 e0 s2 e1 e2
s0 s1 e0 s2 e2 e1 //start A, start B, finish A, start C, finish C, finish B
s0 s1 e0 e1 s2 e2
s0 s1 e1 s2 e0 e2
s0 s1 e1 s2 e2 e0
s0 s1 e1 e0 s2 e2
s0 e0 s1 s2 e1 e2
s0 e0 s1 s2 e2 e1
s0 e0 s1 e1 s2 e2
15页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56217214
复制相关文章
相似问题
腾讯云开发者
