如何在Python中连接链接以获得循环?

发布于 12-26 04:38 字数 288 浏览 5 评论 0原文

我有一个链接列表,想知道连接的路径/循环。

我的链接如下所示:

[[0, 3], [1, 0], [3, 1]]

我希望答案是这样的循环(或任何其他匹配的循环):

[0,3,1]

因此,您采用第一个子列表的第一个元素,然后采用第二个元素,然后查找下一个子列表有了这个元素,你就可以重新开始。

有没有一种优雅的方法来实现这一点?我尝试了reduce 函数,但是必须以链接匹配的方式对链接进行排序。

I have a list of links and want to know the joined path/cycle.

My links look like this:

[[0, 3], [1, 0], [3, 1]]

And I want the answer to be a cycle like that (or any other matching cycle):

[0,3,1]

So you take the first element of the first sublist, then you take the second element and you look for the next sublist starting with this element, and you start all over again.

Is there an elegant way to accomplish this? I tried the reduce function but then the links have to be sorted in a way that the links match.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(7

〆凄凉。2025-01-02 04:38:11

使用生成器有一种非常优雅的方法:

def cycle(lst, val, stop=None):
    d = dict(lst)
    stop = stop if stop is not None else val
    while True:
        yield val
        val = d.get(val, stop)
        if val == stop: break

首先,它允许自然迭代:

>>> for x in cycle([[0, 3], [1, 0], [3, 1]], 0):
....    print x
....
0
3
1

其次,它允许轻松创建列表:

>>> list(cycle([[0, 3], [1, 0], [3, 1]], 0))
[0, 3, 1]

最后,它允许无限的项目生成:

>>> generator = cycle([[0, 3], [1, 0], [3, 1]], 0, Ellipsis)
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3

There is a very elegant way to do it using a generator:

def cycle(lst, val, stop=None):
    d = dict(lst)
    stop = stop if stop is not None else val
    while True:
        yield val
        val = d.get(val, stop)
        if val == stop: break

Firstly, it allows natural iteration:

>>> for x in cycle([[0, 3], [1, 0], [3, 1]], 0):
....    print x
....
0
3
1

Secondly, it allows to create a list easily:

>>> list(cycle([[0, 3], [1, 0], [3, 1]], 0))
[0, 3, 1]

And eventually, it allows infinite item generation:

>>> generator = cycle([[0, 3], [1, 0], [3, 1]], 0, Ellipsis)
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3
橘味果▽酱2025-01-02 04:38:11

考虑使用 networkx 包:

import networkx as nx
G = nx.DiGraph() #creates directed graph
G.add_edges_from([[0, 3], [1, 0], [3, 1]])
print nx.simple_cycles(G).pop()[:-1]

输出:

>> [0, 3, 1]

Consider using the networkx package:

import networkx as nx
G = nx.DiGraph() #creates directed graph
G.add_edges_from([[0, 3], [1, 0], [3, 1]])
print nx.simple_cycles(G).pop()[:-1]

The output:

>> [0, 3, 1]
拧巴小姐2025-01-02 04:38:11

我会看一下 python-graph

提供的功能和算法:

...

  • 周期检测

I'd take a look at python-graph:

Provided features and algorithms:

...

  • Cycle detection
终难愈2025-01-02 04:38:11

把它变成一本字典,然后循环浏览它。

def get_cycles(links):
    """Get a list of all cycles given a list of links"""
    links_dict = dict(links)
    ret = []
    ret_sets = []
    for starting_point in links_dict:
        cycle = []
        x = starting_point
        while x != None:
            cycle.append(x)
            x = links_dict.get(x)
            if x == starting_point:
                break
        # make sure the cycle is not a repeat (and was a cycle)
        if x != None:
            cycle_set = set(cycle)
            if cycle_set not in ret_sets:
                    ret.append(cycle)
                    ret_sets.append(cycle_set)
    return ret

assert get_cycles([[0, 3], [1, 0], [3, 1]]) == [[0, 3, 1]]
assert get_cycles([[0, 3], [1, 0], [3, 1], [5, 2]]) == [[0, 3, 1]]
assert get_cycles([[0, 3], [1, 0], [3, 1], [5, 2], [2, 5]]) == [[0, 3, 1], [2, 5]]

Turn it into a dictionary, and cycle through it.

def get_cycles(links):
    """Get a list of all cycles given a list of links"""
    links_dict = dict(links)
    ret = []
    ret_sets = []
    for starting_point in links_dict:
        cycle = []
        x = starting_point
        while x != None:
            cycle.append(x)
            x = links_dict.get(x)
            if x == starting_point:
                break
        # make sure the cycle is not a repeat (and was a cycle)
        if x != None:
            cycle_set = set(cycle)
            if cycle_set not in ret_sets:
                    ret.append(cycle)
                    ret_sets.append(cycle_set)
    return ret

assert get_cycles([[0, 3], [1, 0], [3, 1]]) == [[0, 3, 1]]
assert get_cycles([[0, 3], [1, 0], [3, 1], [5, 2]]) == [[0, 3, 1]]
assert get_cycles([[0, 3], [1, 0], [3, 1], [5, 2], [2, 5]]) == [[0, 3, 1], [2, 5]]
绝不服输2025-01-02 04:38:11

尝试一下,假设链接列表中仅存在一个循环:

def cycle_list(links):
    d = dict(links)
    ele = links[0][0]
    nxt = d[ele]
    lst = [ele]
    seen = set(lst)
    while nxt not in seen:
        lst.append(nxt)
        seen.add(nxt)
        ele = nxt
        nxt = d[ele]
    return lst

以您的示例为例:

cycle_list([[0, 3], [1, 0], [3, 1]])
> [0, 3, 1]

如果链接列表中可能存在多个循环(您在问题中没有提及),那么您'最好使用大卫罗宾逊的答案。

Try this, assuming that only a single cycle is present in the list of links:

def cycle_list(links):
    d = dict(links)
    ele = links[0][0]
    nxt = d[ele]
    lst = [ele]
    seen = set(lst)
    while nxt not in seen:
        lst.append(nxt)
        seen.add(nxt)
        ele = nxt
        nxt = d[ele]
    return lst

With your example:

cycle_list([[0, 3], [1, 0], [3, 1]])
> [0, 3, 1]

If it's possible that more than one cycle exists in the list of links (you don't mention it in the question), then you're better off using David Robinson's answer.

So要识趣2025-01-02 04:38:11

如果您知道存在一个循环并且所有链接都在循环中(或者至少方向上没有“分裂”,这意味着从任何给定点只有一种方式< /strong>),您可以使用它:

def get_cycle(data):
    d = dict(data)
    first = data[0][0]
    current = d[first]
    path = [first]
    while True:
        if current == first:
            return path
        else:
            path.append(current)
            current = d[current]

它的作用是从第一个链接的第一个点开始遍历给定的数据。然后它只跟踪所有链接,直到到达路径的开头。当它到达路径的开头时,它返回该路径。

很简单,而且我相信它非常有效。

If you know there is a cycle and all the links are in the cycle (or at least there are no "splits" in the directions, meaning there is only one way from any given point), you can use this:

def get_cycle(data):
    d = dict(data)
    first = data[0][0]
    current = d[first]
    path = [first]
    while True:
        if current == first:
            return path
        else:
            path.append(current)
            current = d[current]

What it does is walking through the given data, beginning with the first point of the first link. Then it just follows all the links until it reaches the beginning of the path. When it reaches the beginning of the path, it returns the path.

Simple and I believe it is pretty efficient.

何必那么矫情2025-01-02 04:38:11

使用 itertools.permutations,这将为您提供一组唯一的循环:

import itertools

g = [(0,3), (1,0), (3,1), (1,4), (4,3)]

cycles = {}
for edges in itertools.permutations(g):
    start = prev = edges[0]
    for i, edge in enumerate(edges[1:], start=1):
        if prev[1] != edge[0]:
            break
        if edge[1] != start[0]:
            prev = edge
            continue
        cycles.update({tuple(sorted(edges[0:i+1])): edges[0:i+1]})
        break

result = []
for cycle in cycles.values():
    result.append([edge[0] for edge in cycle])

print result

本例中的结果为 [[3, 1, 0], [4, 3, 1]]

Using itertools.permutations, this will get you the set of unique cycles:

import itertools

g = [(0,3), (1,0), (3,1), (1,4), (4,3)]

cycles = {}
for edges in itertools.permutations(g):
    start = prev = edges[0]
    for i, edge in enumerate(edges[1:], start=1):
        if prev[1] != edge[0]:
            break
        if edge[1] != start[0]:
            prev = edge
            continue
        cycles.update({tuple(sorted(edges[0:i+1])): edges[0:i+1]})
        break

result = []
for cycle in cycles.values():
    result.append([edge[0] for edge in cycle])

print result

the result in this case being [[3, 1, 0], [4, 3, 1]]

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文