Нахождение перекрывающихся чисел в кортеже в Python - PullRequest
Новая
       9

Нахождение перекрывающихся чисел в кортеже в Python

0 голосов
/ 21 февраля 2019

Я работаю над проектом НЛП, и у меня есть список с интервалами символов в некотором тексте.Этот список может выглядеть следующим образом: 

 [(1,4),(1,7),(4,9),(8,15)]

Поэтому моя задача - вернуть все непересекающиеся пары.Если две или более пары чисел перекрываются, то должна быть возвращена пара с самым длинным интервалом.В моем примере я хочу вернуть [(1,7),(8,15)].Как я могу это сделать?

РЕДАКТИРОВАТЬ

Я не хочу объединять свои интервалы, как в Слияние перекрывается здесь .Но я не хочу возвращать все пары / интервалы / кортежи, кроме случаев, когда значения в некоторых кортежах перекрываются.например, (1,4) и (1,7) перекрываются, (4,9) перекрываются с (1,4) и (1,7).Если есть некоторое перекрытие, я хочу вернуть кортеж с наибольшим интервалом, например (1,7) = интервал 7, (1,4) = интервал 4, (4,9) = интервал 5. Это означает, что он должен вернуться (1,7) и (8,15), а также (8,15) не перекрываются (1,7)

1 Ответ

0 голосов
/ 21 февраля 2019

Я не слишком много думал об этом, но следующий подход должен помочь: 

spans = [(1,4),(1,7),(4,9),(8,15)]

del_in = []

for x in spans:
  if spans.index(x) in del_in: continue
  for y in spans:
    if spans.index(y) in del_in: continue
    if x == y: continue
    if len(set(list(range(x[0],x[1]+1))) & set(list(range(y[0],y[1]+1)))) > 0:
      if len(list(range(x[0],x[1]+1))) > len(list(range(y[0],y[1]+1))):
        del_in.append(spans.index(y))
        spans.pop(spans.index(y))
      elif len(list(range(y[0],y[1]+1))) > len(list(range(x[0],x[1]+1))):
        del_in.append(spans.index(x))
        spans.pop(spans.index(x))

print(spans)

Выведет: 

[(1, 7), (8, 15)]

Краткое объяснение: Мы начинаем перебиратьсписок пролетов (итерация x).Для каждого кортежа мы снова итерируем по списку (итерация y), пренебрегая кортежем из x (if x == y: continue).Затем мы преобразуем каждый кортеж в список (например, (1,4) - [1, 2, 3, 4]) с помощью list(range()) и сравниваем списки (насколько это возможно с set()), чтобы увидеть, имеют ли они какой-либо общий элемент.Если длина возвращаемого объекта больше 0, мы сравниваем длину двух списков, чтобы увидеть, какой из них мы оставляем (тот, который имеет больший промежуток).Впоследствии мы удаляем элемент с меньшим интервалом из нашего списка (с .pop()).Поскольку наши итерации x и y все еще проходят наш первоначальный список, нам нужно реализовать механизм, который не позволит сценарию сравнивать элементы с уже удаленными записями.Следовательно, мы работаем с дополнительным списком, содержащим умершие индексы записей, которые мы уже удалили (и оставляем их в двух циклах).

Возможно, есть лучший способ сделать это, но это определенно работает для вашегопример.

...