Объединить два подсписка в одном списке в один подсписок python

Question

У меня есть словарь, в котором есть список с парными номерами в качестве подсписка, Я пытаюсь проверить, не перекрывается ли подсписки.

{'5ykw.pdb': [[10, 22], [33, 40], [39, 51], [63, 71], [94, 105]]}

Существует перекрытие между [33, 40] и [39, 51], и поэтому я хочу объединить их, чтобы сделать:

{'5ykw.pdb': [[10, 22], [33, 51], [63, 71], [94, 105]]}

Answer 1

Вы можете «перекрыть» список, просто используя эту функцию:

def deoverlap(lst):
    if not lst:
        return []
    lst = [sorted(pair) for pair in lst]  # sort pairs (leave out if not needed)
    lst = sorted(lst)  # sort by first item (breaking ties by second item)
    out = []
    prev = lst[0]
    for pair in lst[1:]:
        if prev[1] >= pair[0]:
            if prev[1] < pair[1]:
                prev[1] = pair[1]
        else:
            out.append(prev)
            prev = pair
    out.append(prev)
    return out

dct = {'5ykw.pdb': [[10, 22], [33, 40], [39, 51], [63, 71], [94, 105]]}

dct['5ykw.pdb'] = deoverlap(dct['5ykw.pdb'])

print(dct)  # prints {'5ykw.pdb': [[10, 22], [33, 51], [63, 71], [94, 105]]}

Единственное допущение здесь заключается в том, что входные данные для deoverlap() представляют собой список пар сопоставимого типа (обычно чисел), где каждая пара представляет собой список длиной 2.

Пары сортируются внутри, затем сортируются по первому элементу, а затем объединяются, если максимум предыдущей пары ≥ минимума текущей пары. Если слияние не должно происходить, когда они равны, 9 ^th строка deoverlap() должна стать

        if prev[1] > pair[0]:

Answer 2

Вы можете использовать рекурсивную форму поиска в ширину:

def overlap(a, b) -> bool:
  return a[-1] >= b[0] and a[-1] < b[-1]

def group(d, _c, seen):
   return [_c, 
     [i if i not in seen else group(d, i, seen+[i]) for i in d if overlap(_c, i)]]

r = {'5ykw.pdb': [[10, 22], [33, 40], [39, 51], [63, 71], [94, 105]]}
new_data = [group(r['5ykw.pdb'], i, []) for i in r['5ykw.pdb'] if not any(overlap(c, i) for c in r['5ykw.pdb'])]
final_data = [a if not b else [a[0], max(h for _, h in b)] for a, b in new_data]

Выход:

[[10, 22], [33, 51], [63, 71], [94, 105]]

Это также будет работать при вводе с большим числом перекрытий:

r = {'5ykw.pdb':[[15, 20], [18, 21], [19, 30]]}
new_data = [group(r['5ykw.pdb'], i, []) for i in r['5ykw.pdb'] if not any(overlap(c, i) for c in r['5ykw.pdb'])]
final_data = [a if not b else [a[0], max(h for _, h in b)] for a, b in new_data]

Выход:

[[15, 30]]

Answer 3

Вы можете использовать reduce с пользовательской функцией merge для создания нового списка:

from functools import reduce

def merge(acc, curr):
    if not len(acc) or acc[-1][1] < curr[0]:
        acc.append(curr)
        return acc
    acc[-1][1] = curr[1] # update last element in accumulator
    return acc

data = {'5ykw.pdb': [[10, 22], [33, 40], [39, 51], [63, 71], [94, 105]]}
data['5ykw.pdb'] = reduce(merge, data['5ykw.pdb'], [])
print(data)
# {'5ykw.pdb': [[10, 22], [33, 51], [63, 71], [94, 105]]}