python - 合并重叠 (str) 对象

Question

问题如下:

我想离开这个设置

{'A/B', 'B/C', 'C/D', 'D/E', ..., 'U/V', 'V/W', ..., 'X/Y', ..., 'Z', ...}

到这个集合

{'A/B/C/D/E', ..., 'U/V/W', ..., 'X/Y', ..., 'Z', ...}

其中对象 A、B、C ... 只是字符串。输出解决方案应独立于对象出现的顺序(即，如果您打乱集合中的对象，解决方案应始终相同)

换句话说，我想合并重叠的对象。

以下形式的输入不会发生:

{"A/B", "B/C", "B/D"}
{"A/B", "B/C", "C/A"}

可以有不带'/'的对象。

这是我想出的部分解决方案:

    example={'A/B', 'B/C', 'C/D', 'D/E','U/V', 'V/W','X/Y'}
    
    def ext_3plus(unit):
        for couple in list(itertools.combinations(list(unit),2)):
            if '/' in couple[0] and '/' in couple[1]:
                if couple[0].split('/')[0]==couple[1].split('/')[1]:
                    unit.remove(couple[0])
                    unit.remove(couple[1])
                    unit.add(couple[1].split('/')[0]+'/'+couple[0])
                if couple[0].split('/')[1]==couple[1].split('/')[0]:
                    unit.remove(couple[0])
                    unit.remove(couple[1])
                    unit.add(couple[0]+'/'+couple[1].split('/')[1])
            else: #the input can contain object not having '/'
                continue

有两个问题，首先它只做一次迭代，{'A/B', 'B/C', 'C/D', 'D/E','U/V', 'V/W','X/Y'}

是:

{'A/B/C', 'C/D/E', 'U/V/W', 'X/Y'}

其次，如果我包含不包含 '/' 的对象，则输入为 {'A/B', 'B/C', 'C/D', 'D/E','U/V', 'V/W','X/Y','Z'，结果和前面的不一样:

{'A/B', 'B/C/D', 'D/E', 'U/V/W', 'X/Y', 'Z'}

所以应该在第一次迭代时进行递归调用等。应该怎么做？

Answer 1

如果我理解正确，这可以看作是一个图形问题，并这样解决:

import networkx as nx

example = {'A/B', 'B/C', 'C/D', 'D/E', 'U/V', 'V/W', 'X/Y', "Z"}

# convert each string to a and edge
# each pattern to the side of / is a node
edges = [tuple(s.split("/")) for s in example if "/" in s]

nodes = [s for s in example if "/" not in s]

# create directed graph from edges
g = nx.from_edgelist(edges, create_using=nx.DiGraph)
g.add_nodes_from(nodes)

# find each path using topological sort
runs, current = [], []
for e in nx.topological_sort(g):
    # start a new path each time a node with in-degree 0
    # in-degree 0 means it is the start of a new path
    if g.in_degree(e) == 0:
        if current:
            runs.append(current)
            current = []
    current.append(e)

if current:
    runs.append(current)

# format the result
result = ["/".join(run) for run in runs]
print(result)

输出

['Z', 'U/V/W', 'X/Y', 'A/B/C/D/E']

如果我没记错的话，这种方法的总体复杂度为 O(n)。有关拓扑排序的更多信息，请参见 here .

更新

在 networkx 2.6.4 中使用 lexicographical_topological_sort