Как «объединить» перекрывающийся диапазон с неперекрывающимся диапазоном?

Question

Вопрос: Кто-нибудь может предложить лучший или более питонический подход к сокращению перекрывающихся пар диапазонов до непересекающихся пар диапазонов?

Справочная информация: у меня есть список кортежей, представляющих начальную и конечную пары.Я пытаюсь по существу завершить объединение всех пар начальных концов.Входные конечные пары имеют перекрывающиеся значения, и выходные данные должны представлять входные начальные конечные пары без какого-либо перекрытия.

Приведенный ниже код является близким, но неверным, поскольку он выводит дополнительный диапазон, которого не было на входе (я такжепонимаю, что это не очень хорошо, и почему это неправильно).Кто-нибудь может предложить лучший подход или какую-то встроенную функцию, которую я упустил из виду?

Извинения за основной вопрос.Спасибо за помощь!

##create example data
pairA =[(0,5),(10,12)]
pairB =[(1,2),(11,15)]
pairC =[(1,4),(10,12),(15,17)]

#combine the lists to one list
#ultimately may have n number of lists and felt it would be easier to
merged = pairA + pairB +pairC
# produce union of list * unpacks the arguments of a list
listUnion= sorted(set().union(*merged))

#this is the piece of code I am looking at improving
#it creates new start end pairs based on the union
lastElement =listUnion[-1]
outList=[]

for item in listUnion:
    #create start end pair from value i and i+1
    if item != lastElement:
        outList.append((item,listUnion[listUnion.index(item)+1]))
    else:
        #last element of the list, becomes the last element of list pair
        #it can be ignored
        pass
print outList 
"""output: [(0, 1), (1, 2), (2,4), (4, 5), (5, 10), (10, 11), (11, 12), (12, 15), (15, 
17)]
correct output: would not have (5,10) as there is no overlap here in the input """

Редактировать: Добавлено визуальное представление проблемы

Answer 1

Не могли бы вы прояснить проблему, пожалуйста.Я вижу, что [(0,5), (1,2)] производит [(0, 1), (1, 2), (2, 5)].Что бы [(0,5), (1,5)] произвело бы, [(0, 1), (1, 5), (5, 5)], или просто [(0,1)], или что-то еще?

Answer 2

Вот решение.Это, вероятно, не очень питонический, потому что мой опыт работы с Python очень ограничен, но он работает.

pairs_a = [(0, 5), (10, 12)]
pairs_b = [(1, 2), (11, 15)]
pairs_c = [(1, 4), (10, 12), (15, 17)]

merged = pairs_a + pairs_b + pairs_c
merged.sort()

set_list = []
cur_set = set()
cur_max = merged[0][1]
for pair in merged:
    p0, p1 = pair
    if cur_max < p0:
        set_list.append(cur_set)
        cur_set = set()
    cur_set.add(p0)
    cur_set.add(p1)
    if cur_max < p1:
        cur_max = p1
set_list.append(cur_set)

out_list = []
for my_set in set_list:
    my_list = sorted(my_set)
    p0 = my_list[0]
    for p1 in my_list[1:]:
        out_list.append((p0, p1))
        p0 = p1

# more pythonic but less readable in spite of indentation efforts:
# out_list = [pair
#             for zipped in [zip(list[:-1], list[1:])
#                            for list in [sorted(set)
#                                         for set in set_list]]
#                 for pair in zipped]

# alternate ending:
# out_list = [sorted(set) for set in set_list]

print(out_list)

Идея состоит в том, чтобы сначала отсортировать все пары диапазонов по первому элементу.Это то, что делает merged.sort() (для устранения неоднозначности используются последовательные члены кортежа, но здесь это неважно).Затем мы перебираем отсортированные пары диапазонов, и, пока мы находимся в куче перекрывающихся диапазонов, мы добавляем все начало и конец к текущему набору.Чтобы узнать, когда заканчивается группа, мы сохраняем максимум всех концов диапазона.Как только начинается диапазон, выходящий за пределы этого максимума, мы сохраняем текущий набор, добавляя его в список, и начинаем новый.Последний набор должен быть добавлен в список после цикла.Теперь у нас есть список наборов, который мы можем легко перевести в список списков или в список пар.

Answer 3

Не уверен в ваших ограничениях среды, но если у вас их нет, вы можете подумать об этом: https://pypi.org/project/intervaltree/ в частности,

result_tree = tree.union(iterable)