python - 组织元组列表

Question

我有一个动态创建的元组列表。

列表显示为:

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

list 的每个元组(a, b) 表示某个表的索引范围。

范围 (a, b) 和 (b, d) 在我的情况下与 (a, d) 相同

我想合并第二个元素与第一个元素匹配的元组。

因此，在上面的示例中，我想合并 (8, 10), (10,13) 以获得 (8,13) 并删除 (8, 10), (10,13)

(19,25) 和 (25,30) 合并应该产生 (19, 30)

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

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

Answer 1

如果您需要在评论中考虑诸如 skovorodkin 的示例之类的内容，

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

(或更复杂的示例)，那么一种有效的方法就是使用图表。

假设您创建了一个有向图(可能使用 networkx )，其中每一对都是一个节点，并且从 (a, b) 到节点 (c, d ) 如果 b == c。现在运行 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。我们必须递归地遍历事物，但要记住我们已经访问过的事物。

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

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