在Python中像Domino一样对元组进行排序/查找顶点连通性 [英] Sorting tuples in Python like dominoes/ finding vertex connectivity

问题描述

我有一个像这样的整数元组列表:

I have a list of integer tuples like this:

L=[(1,2),(7,6),(2,3),(8,5),(3,8),(5,7)]

每对在两个顶点之间定义一个边，我想找到顶点连通性. 没有循环，元组总是像多米诺骨牌一样唯一地链接在一起，因此在这种情况下，排序后的列表应如下所示:

Each pair defines an edge between two vertices and I want to find the vertex connectivity. There are no loops, the tuples always uniquely link up like dominoes so in this case the sorted list should look like:

L_sorted=[(1,2),(2,3),(3,8),(8,5),(5,7),(7,6)]

或者

L_sorted=[1,2,3,8,5,7,6]

有没有一种有效的方法可以在Python中使用预定义的方法进行此类排序?

Is there an efficient way to do sorting like this in Python using predefined methods?

推荐答案

我认为没有任何内置功能可以解决此问题.第三方库可能会有所帮助.您可以使用纯python解决此问题:

I do not think that any built-in facility can solve this. Third-party libraries might help. You can solve it in pure python:

L=[(1,2),(7,6),(2,3),(8,5),(3,8),(5,7)]
def domino(l):
    start = cursor = l[0][0]
    d = dict(l)
    while True:
        yield cursor
        try:
            cursor = d[cursor]
        except KeyError:
            # return here if your input may be non-cyclic.
            raise
        if cursor==start:
            return
x = list(domino(L))
# raises KeyError because 6 is dangling...

...或使用 ctypes .

这篇关于在Python中像Domino一样对元组进行排序/查找顶点连通性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！