区间关系组合的生成算法

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (13)

我想生成一些用于处理不同类型间隔的样本数据,并希望确保表示所有可能的间隔关系。

就我的目的而言,{ meet,overlap,is-finished-by }是等价的,equals可以被忽略,{ B开始A,A包含B }也是等价的。我还假设所有的间隔都被排序和标记,使得A在B之前开始,在C之前开始。所以我基本上对三种情况感兴趣:

  • A之前的A(例如A = [1,2],B = [3,4])
  • A含有B(例如A = [1,4],B = [2,3])
  • 重叠B(例如A = [1,3],B = [2,4])

引入第三个间隔会产生更多情况:

  • A之前的B,C之前的B(例如A = [1,2],B = [3,4],C = [5,6])
  • 在B之前,B包含C(例如A = [1,2],B = [3,6],C = [4,5])
  • A之前的B,B与C重叠(例如A = [1,2],B = [3,5],C = [4,6])
  • ...

虽然在B之前的A的情况下,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

图片来源: Höppner,Frank&Topp,亚历山大。(2007年)。基于随时间变量轨迹的分类。739-749。10.1007 / 978-3-540-77226-2_74。

编辑:根据MBo的答案,为四个时间间隔添加了解决方案的可视化。

提问于
用户回答回答于

有(2 * n-1)!! (n个奇数的双阶乘)组合用于n个区间,序列是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

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励