在Python中获取链接列表中最长的链接

Question

我有一个如下的边列表：

edges_1 = ['a::b::c', 'a::b', 'a', 'a::d','a::d::e', 'a::d::e::f']
edges_2 = ['a', 'b', 'c']

我正在尝试编写一个函数，该函数返回最长的链接.. 对于上述情况，该函数将返回

['a::b::c','a::d::e::f']

and for second case

['a', 'b', 'c']

我认为可以使用networkx构建图形，然后遍历最长序列。但是我想知道是否有其他数据结构或方法可以解决这个问题。

- frazman

---

不清楚为什么你期望在第一个情况的结果中出现 'a::b::c'。 - Nir Alfasi

@alfasin：好问题。把边想象成一个图形。所以，我们有两个边缘：a->b->c 和 a->d->e->f。其他的都在中间。我想要的是这些最终完整的边缘，而不是现在的 a、a->b 等等。这样说你明白了吗？ - frazman

我认为还不够清楚，你所说的“其他所有东西都在中间”是什么意思？ - bones.felipe

Answer 1

我认为这个问题与“上集合”的概念有关。

以下是一种解决方案，将您的结构转换为边集的列表。然后，它会查看每个集合是否有另一个列表成员是其自身的上集合。

def has_upset(down, set_list):
    return any(down.intersection(s) == down for s in set_list if s != down)

def filter_downsets(set_list):
    return filter(lambda d: not has_upset(d, set_list), set_list)

这里是用法（包括将你的结构转换为集合形式）。

edges_1 = ['a::b::c', 'a::b', 'a', 'a::d','a::d::e', 'a::d::e::f']
edges_2 = ['a', 'b', 'c']

edge_sets_1 = [set(e.split('::')) for e in edges_1]
print filter_downsets(edge_sets_1)
# [set(['a', 'c', 'b']), set(['a', 'e', 'd', 'f'])]

edge_sets_2 = [set(e.split('::')) for e in edges_2]
print filter_downsets(edge_sets_2)
# [set(['a']), set(['b']), set(['c'])]

- Jared Goguen

Answer 2

根据您在评论中的注释，我修改了代码。

假设这些图是有向无环图，并且目标是消除列表中其他序列的子序列。

我们可以不再查看每个序列的长度，而是仅丢弃任何是其他序列子集的序列。为此，我们可以使用str子集运算符。

print(f"Initial list: {edges_1}")
keepers = []

for edge in edges_1:
    other_edges = edges_1[:]
    other_edges.remove(edge)
    print(f"Test {edge} against {other_edges}")
    for rest in other_edges:
        if edge in rest:
            # Discard any edges that are subsets an an edge in `other_edges`
            print(f"Found match {edge} -> {rest}")
            break
    else:
        # If the edge hasn't been discarded, it is a "longest edge"
        keepers.append(edge)
        print(f"No greater matches found for {edge}")

print(f"The longest edges: {keepers}")

这段代码并不是最高效、也不是最整洁的，但它能突出基本的解决问题机制。

旧答案：在没有更多 OP 描述的情况下解决。

如果你可以始终假设顶点之间的边由“::”表示，那么你可以使用一些简单的字符串处理来获取每个序列的长度。

这个解决方案假设你总是想要最长的两个序列。

edges_1 = ['a::b::c', 'a::b', 'a', 'a::d','a::d::e', 'a::d::e::f']
edges_2 = ['a', 'b']

def print_longest_two_sequences(edges):
    links = [edge.split("::") for edge in edges]
    links.sort(key=len, reverse=True)
    links = ["::".join(edge) for edge in links]
    print(links[:2])

print_longest_two_sequences(edges_1)
print_longest_two_sequences(edges_2)

- Nathaniel Rivera Saul

---

谢谢回复，但如果我有edges_1 = ['a::b::c'，'a::b'，'a'，'a::d'，'a::d::e'，'a::d::e::f'，'a::d::e::g']，那么这将无法工作。在这种情况下，它应该返回'a::b::c'，'a::d::e::f'和'a::d::e::g'。此外，2不是硬编码的..例如edges_2 = ['a'，'b'，'c']。 - frazman

听起来你的问题定义不太清楚。为什么你不希望它返回'a::d::e'呢？你怎么知道它应该返回哪些序列？最长的？最长的几个？所有长度大于某个特定长度的序列？ - Nathaniel Rivera Saul

把边想象成一个图，我们有两条边：a->b->c 和 a->d->e->f。其他的都在中间。我想要的是这些最终完整的边，而不是现在的样子，即 a，a->b 等等。明白我的意思吗？所以，a::d::e 不返回，因为有一条更大的链接 a->d->e->f 和 a->d->e->g。 - frazman

你的图是一个有向无环图吗？如果不是，最长序列如何定义？没有重复节点？ - bones.felipe

@bones.felipe: 是的 - frazman