Алгоритм генерации комбинаций интервальных отношений - PullRequest
Новая
       18

Алгоритм генерации комбинаций интервальных отношений

1 голос
/ 20 мая 2019

Я хотел бы сгенерировать некоторые примерные данные для обработки различных типов интервалов и хотел бы обеспечить представление всех возможных взаимосвязей интервалов.

Overview of different relationships between intervals

Для моих целей { соответствует, перекрывается, завершено на } эквивалентно, равно можно игнорировать и { B запускает A, A содержит B } также эквивалентны. Я также предполагаю, что все интервалы отсортированы и помечены так, что A начинается до B, который начинается до C и т. Д. Поэтому я, по сути, заинтересован в трех случаях:

  • A до B (например, 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,6])
  • ...

И хотя в случае с А до В, из этого следует, что А всегда будет также и до С, но это не относится к другим вариантам, где нам также необходимо рассмотреть отношения А и С:

  • 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). Классификация, основанная на отслеживании переменных во времени. 739-749. 10,1007 / 978-3-540-77226-2_74.

РЕДАКТИРОВАТЬ: Добавлена ​​визуализация решения для четырех интервалов, на основе ответа MBo. enter image description here

1 Ответ

2 голосов
/ 20 мая 2019

Есть (2 * n-1) !! ( двойной факториал для нечетных чисел) комбинации для 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
...