传递闭包python元组

Question

有没有人知道是否有内置的python用于计算元组的传递闭包？

我有形式的元组,(1,2),(2,3),(3,4)我想要得到(1,2),(2,3),(3,4),(1,3)(2,4)

谢谢.

Answer 1

传递闭包没有内置功能.

它们实现起来非常简单.

这是我的看法:

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

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