组织元组列表

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)

我不知道从哪里开始.元组不重叠.

编辑:我一直试图避免任何类型的for循环,因为我有一个非常大的列表

Answer 1

如果您需要在评论中考虑skovorodkin的例子,

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

(或者更复杂的例子),那么一种有效的方法就是使用图表.

假设您创建了一个有向图(可能正在使用networkx),其中每对都是一个节点,如果b == c ,则从(a,b)到节点(c,d)有一条边.现在运行拓扑排序,根据顺序迭代,并相应地合并.您应该小心处理具有两个(或更多)传出边缘的节点.

我意识到你的问题表明你想要避免因长列表大小而导致的循环.相反,对于长列表,我怀疑你甚至会发现使用列表理解(或类似的东西)的有效线性时间解决方案.请注意,您无法在线性时间内对列表进行排序.

这是一个可能的实现:

假设我们开始

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.我们必须以递归的方式遍历事物,但要记住我们已经访问过的内容.

让我们创建一个我们访问过的词典:

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 2

如果它们不重叠,那么您可以对它们进行排序,然后将它们组合起来.

这是一个产生新元组的生成器:

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 3

非递归方法，使用排序（我添加了更多节点来处理复杂的情况）：

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)]

唯一的缺点是原始排序顺序没有保留。不知道是不是有问题。