传递闭包 Python 元组

Question

有没有人知道Python里有没有内置的方法可以计算元组的传递闭包？

我有一些元组，比如(1,2),(2,3),(3,4)，我想得到(1,2),(2,3),(3,4),(1,3)(2,4)这样的结果。

谢谢。

Answer 1

我们可以从一个“起始节点”开始，进行“闭包”操作。这个过程就是不断地把当前“端点”的“图边”合并，直到找不到新的端点为止。我们最多需要进行（节点数量 - 1）次这样的操作，因为这就是路径的最大长度。（这样做可以避免在有环的情况下陷入无限递归；虽然在一般情况下可能会浪费一些迭代，但可以省去检查我们是否完成的工作，也就是在某次迭代中没有做出任何改变。）

from collections import defaultdict

def transitive_closure(elements):
    edges = defaultdict(set)
    # map from first element of input tuples to "reachable" second elements
    for x, y in elements: edges[x].add(y)

    for _ in range(len(elements) - 1):
        edges = defaultdict(set, (
            (k, v.union(*(edges[i] for i in v)))
            for (k, v) in edges.items()
        ))

    return set((k, i) for (k, v) in edges.items() for i in v)

（我其实测试过一次 ;)）

Answer 2

这是一个简单的尝试：

def transitive_closure(elements):
    elements = set([(x,y) if x < y else (y,x) for x,y in elements])

    relations = {}
    for x,y in elements:
        if x not in relations:
            relations[x] = []
        relations[x].append(y)

    closure = set()
    def build_closure(n):
        def f(k):
            for y in relations.get(k, []):
                closure.add((n, y))
                f(y)
        f(n)

    for k in relations.keys():
        build_closure(k)

    return closure

运行它后，我们会得到

In [3]: transitive_closure([(1,2),(2,3),(3,4)])
Out[3]: set([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])

Answer 3

没有内置的功能来处理传递闭包。

不过，实现起来其实很简单。

这是我的做法：

def transitive_closure(a):
    closure = set(a)
    while True:
        new_relations = set((x,w) for x,y in closure for q,w in closure if q == y)

        closure_until_now = closure | new_relations

        if closure_until_now == closure:
            break

        closure = closure_until_now

    return closure

调用： transitive_closure([(1,2),(2,3),(3,4)])

结果： set([(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (2, 4)])

调用： transitive_closure([(1,2),(2,1)])

结果： set([(1, 2), (1, 1), (2, 1), (2, 2)])

传递闭包 Python 元组

7 个回答

撰写回答