问区间关系组合的生成算法

EN

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

​

​

对于我来说，{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

图片来源：Höppner, Frank & Topp, Alexander. (2007). Classification Based on the Trace of Variables over Time. 739-749. 10.1007/978-3-540-77226-2_74.

编辑:根据MBo的回答，添加了四个区间的解决方案可视化。

​