Algorithm for generating combinations of interval relationships

Question

I'd like to generate some sample data for processing different types of intervals, and would like to ensure that all possible relationships of intervals are represented.

For my purposes, {meets, overlaps, is-finished-by} are equivalent, equals can be ignored and {B starts A, A contains B} are also equivalent. I will also assume that all of the intervals are sorted and labelled such that A starts before B, which starts before C etc. So I am essentially interested in three cases:

• A before B (e.g. A=[1,2], B=[3,4])
• A contains B (e.g. A=[1,4], B=[2,3])
• A overlaps B (e.g. A=[1,3], B=[2,4])

Introducing a third interval produces several more cases:

• A before B, B before C (e.g. A=[1,2], B=[3,4], C=[5,6])
• A before B, B contains C (e.g. A=[1,2], B=[3,6], C=[4,5])
• A before B, B overlaps C (e.g. A=[1,2], B=[3,5], C=[4,6])
• ...

And although in the case of A before B, it follows that A will always be before C as well, this is not the case for other variations where we also need to consider the relationship of A and C:

• A contains B, B overlaps C, A overlaps C (e.g. A=[1,5], B=[2,4], C=[3,6])
• A contains B, B overlaps C, A contains C (e.g. A=[1,6], B=[2,4], C=[3,5])

How many different combinations of relationships are possible for a given number of intervals?

What is an algorithm that will generate these combinations?

As an example, the algorithm might produce the below output to solve for the case of two intervals:

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

Image Credit: 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.

---

EDIT: Added a visualization of the solution for four intervals, based on MBo's answer.

Answer 1

There are (2*n-1)!! (double factorial for odd numbers) combinations for n intervals, sequence is 1,3,15,105,945...

Quick-made Python implementation to show results. At every stage we can start new interval (greater by 1 than previous start) or finish any opened interval

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