3

我有成对的整数存储在元组中（例如(1,2) (4,5) ...）。这些元组存储在一个列表中。

我试图在这些元组中找到这种模式(1,2) (2,3) (3,4) (4,1)，它以任何整数开头，然后从元组的第二个整数跳到另一个元组的第一个，以开始时拾取的整数结束。

每个模式都存储在一个集合中。然后我将第一个整数和相关模式存储为键/值对。在我的例子中，它变成：dictionary={1:set([1,2,3,4]),...}

然后我合并具有共同项目的模式。例如(1,2) (2,3) (3,1)and(2,4) (4,1)被合并到这个集合中：set([1,2,3,4])。我删除了其中一个键。

这是我的代码：

from collections import defaultdict
dictio_chaine=defaultdict(set)
for item1 in A:               # A is the list containing the afore mentioned tuples
    a,b=item1
    l=[a,b]
    for item2 in A:
        if item2[0]==b and b!=a:
            b=item2[1]
            l.append(b)
        if b==a:
            break
    if l[-1]==a:
        dictio_chaine[a].update(l)

liste=combinations(dictio_chaine.iterkeys(),2)  #The following piece of code merges the
for item in liste:                                            #overlapping patterns.
    if item[0] in dictio_chaine and item[1] in dictio_chaine:
        if dictio_chaine[item[0]]&dictio_chaine[item[1]]:
            dictio_chaine[item[0]].update(dictio_chaine[item[1]])
            del dictio_chaine[item[1]]

我面临以下问题：我的算法的第一部分，它在元组列表中找到模式，非常差，因为它的性能在 O(n^2) 中。

我认为创建一棵树会更好。模式(1,2) (2,3) (3,1)成为2 is the child of 1, 3 is the child of 2 ...

然后，如果(2,5) (5,2)遇到该模式，它将成为一个新的分支 5，它是 2 的子节点，它已经是 1 的子节点。最终，我将合并成一个具有与第一个节点相同的叶子的单个集合分支。

会更好吗？我怎么能实现这样的树，因为我可以轻松实现的唯一树是二叉树，它根本不适合我正在尝试做的事情。

你有什么建议可以帮助我改进我的算法吗？

4

1 回答 1

3

如果我理解这个问题，那么您正试图在有向图中找到简单的循环。

换句话说，您可以将元组（例如 (4,5)）解释为表示节点 4 和节点 5 之间的有向边。然后，您试图找到一条从节点开始的路径，沿着这些边的数量，并且返回起始节点。

您可以使用Python 库NetworkX中的simple_cycles函数轻松完成此操作。例如，

>>> import networkx as nx
>>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
>>> list(nx.simple_cycles(G))
[[2], [2, 1], [2, 0], [2, 0, 1], [0]]

对于 n 个节点、e 个边和 c 个基本电路，时间复杂度为 O((n+e)(c+1))。

于 2013-08-06T09:20:50.130 回答