Организация списка кортежей

Question

У меня есть список кортежей, которые я создаю динамически.

Список выглядит как:

List = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)] 

(a, b) Каждый кортеж из списка представляет собой набор индексов из определенной таблицы.

Диапазоны (a, b) and (b, d) это же в моей ситуации, как (a, d)

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

Так, в приведенном выше примере, я хочу, чтобы объединить (8, 10), (10,13) получить (8,13) и удалить (8, 10), (10,13)

(19,25) and (25,30) слияние должно дать (19, 30)

Я понятия не имею, с чего начать. Кортежи не перекрываются.

Edit: Я пытался просто избегать любого рода цикл, как у меня есть довольно большой список

Answer 1

нерекурсивна подход, используя сортировку (я добавил больше узлов для обработки сложный случай):

l = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30), (30,34), (38,40)] 
l = sorted(l) 

r=[] 
idx=0 

while idx<len(l): 
    local=idx+1 
    previous_value = l[idx][1] 
    # search longest string 
    while local<len(l): 
     if l[local][0]!=previous_value: 
      break 
     previous_value = l[local][1] 
     local+=1 
    # store tuple 
    r.append((l[idx][0],l[local-1][1])) 
    idx = local 


print(r) 

результат:

[(1, 4), (8, 13), (14, 16), (19, 34), (38, 40)] 

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

Answer 2

Если вам необходимо принимать во внимание такие вещи, как, например Сковородкин в комментарии,

[(1, 4), (4, 8), (8, 10)] 

(или даже более сложные примеры), то одним из способов эффективного использования будет использование графиков.

Допустим, вы создать орграф (возможно, с помощью networkx), где каждая пара является узлом, и есть ребро из (а, б) к узлу (C, D), еслиб == гр. Теперь запустите topological sort, итерации в соответствии с порядком и слияния соответственно. Вы должны позаботиться о том, чтобы обрабатывать узлы с двумя (или более) исходящими краями должным образом.

---

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

---

Вот возможная реализация:

Скажем, мы начинаем с

l = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)] 

Это упрощает следующее для удаления дубликатов, так что давайте делать:

l = list(set(l)) 

Теперь, чтобы построить орграф:

import networkx as nx 
import collections 

g = nx.DiGraph() 

Вершины просто пары:

g.add_nodes_from(l) 

Чтобы построить края, нам нужен словарь:

froms = collections.defaultdict(list) 
for p in l: 
    froms[p[0]].append(p) 

Теперь мы можем добавить края:

for p in l: 
    for from_p in froms[p[1]]: 
     g.add_edge(p, from_p) 

Далее две строки не нужны - они просто здесь, чтобы показать, как выглядит график на этом этапе:

>>> g.nodes() 
[(25, 30), (14, 16), (10, 13), (8, 10), (1, 4), (19, 25)] 

>>> g.edges() 
[((8, 10), (10, 13)), ((19, 25), (25, 30))] 

Теперь давайте разберёмся пары по топологической сортировки:

l = nx.topological_sort(g) 

Наконец, вот сложная часть. Результатом будет DAG. Мы должны проходить рекурсивно, но помните, что мы уже посетили.

Давайте создадим Dict, что мы посетили:

visited = {p: False for p in l} 

Теперь рекурсивная функция, что данный узел, возвращает максимальное преимущество в диапазоне от любого узла достижимый от него:

def visit(p): 
    neighbs = g.neighbors(p) 
    if visited[p] or not neighbs: 
     visited[p] = True 
     return p[1] 
    mx = max([visit(neighb_p) for neighb_p in neighbs]) 
    visited[p] = True 
    return mx 

Мы Все готово. Давайте создадим список для конечных пар:

final_l = [] 

и посетить все узлы:

for p in l: 
    if visited[p]: 
     continue 
    final_l.append((p[0], visit(p))) 

Вот конечный результат:

>>> final_l 
[(1, 4), (8, 13), (14, 16)] 

Answer 3

Вот один оптимизированный рекурсии подход:

In [44]: def find_intersection(m_list): 
      for i, (v1, v2) in enumerate(m_list): 
       for j, (k1, k2) in enumerate(m_list[i + 1:], i + 1): 
        if v2 == k1: 
         m_list[i] = (v1, m_list.pop(j)[1]) 
         return find_intersection(m_list) 
      return m_list 

Демонстрация:

In [45]: lst = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)] 

In [46]: find_intersection(lst) 
Out[46]: [(1, 4), (8, 13), (19, 30), (14, 16)] 

Answer 4

Если они не пересекаются, вы можете отсортировать их, а затем просто соединить соседние.

Вот генератор, который дает новые кортежи:

def combine_ranges(L): 
    L = sorted(L) # Make a copy as we're going to remove items! 
    while L: 
     start, end = L.pop(0) # Get the first item 
     while L and L[0][0] == end: 
      # While the first of the rest connects to it, adjust 
      # the end and remove the first of the rest 
      _, end = L.pop(0) 
     yield (start, end) 

print(list(combine_ranges(List))) 

Если скорость важна, используйте collections.deque вместо списка, так что .pop(0) операции могут быть с постоянной скоростью.

Answer 5

Список первых отсортированных и смежных пар (min1, max1), (min2, max2) сливаются вместе, если они перекрываются.

MIN=0 
MAX=1 

def normalize(intervals): 
    isort = sorted(intervals) 
    for i in range(len(isort) - 1): 
     if isort[i][MAX] >= isort[i + 1][MIN]: 
      vmin = isort[i][MIN] 
      vmax = max(isort[i][MAX], isort[i + 1][MAX]) 
      isort[i] = None 
      isort[i + 1] = (vmin, vmax) 
    return [r for r in isort if r is not None] 

List1 = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)] 
List2 = [(1, 4), (4, 8), (8, 10)] 
print(normalize(List1)) 
print(normalize(List2)) 

#[(1, 4), (8, 13), (14, 16), (19, 30)] 
#[(1, 10)] 

Answer 6

Вы можете использовать словарь для сопоставления различных конечных индексов с диапазоном, заканчивающимся на этот индекс; то просто перебирать список отсортирован по индексу начала и объединять сегменты соответственно:

def join_lists(lst): 
    ending = {} # will map end position to range 
    for start, end in sorted(lst): # iterate in sorted order 
     if start in ending: 
      ending[end] = (ending[start][0], end) # merge 
      del ending[start] # remove old value 
     else: 
      ending[end] = (start, end) 
    return list(ending.values()) # return remaining values from dict 

С другой стороны, как отметил Tomer W in comments, вы можете обойтись без сортировки, итерируя список дважды, что делает это решение принимать только линейное время (O (n)) wrt длина списка.

def join_lists(lst): 
    ending = {} # will map end position to range 
    # first pass: add to dictionary 
    for start, end in lst: 
     ending[end] = (start, end) 
    # second pass: lookup and merge 
    for start, end in lst: 
     if start in ending: 
      ending[end] = (ending[start][0], end) 
      del ending[start] 
    # return remaining values from dict 
    return list(ending.values()) 

Примеры вывода, для обоих случаев:

>>> join_lists([(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)]) 
[(1, 4), (8, 13), (14, 16), (19, 30)] 
>>> join_lists(lst = [(1, 4), (4, 8), (8, 10)]) 
[(1, 10)] 

Answer 7

Следующие должны работать. Он разбивает кортежи на отдельные числа, затем находит кортеж, привязанный к каждому кластеру. Это должно работать даже при сложных перекрытиях, например [(4, 10), (9, 12)]

Это очень простое решение.

# First turn your list of tuples into a list of numbers: 
my_list = [] 
for item in List: my_list = my_list + [i for i in range(item[0], item[1]+1)] 

# Then create tuple pairs: 
output = [] 
a = False 
for x in range(max(my_list)+1): 
    if (not a) and (x in my_list): a = x 
    if (a) and (x+1 not in my_list): 
     output.append((a, x)) 
     a = False 

print output