python - 3个列表的融合

Question

很长一段时间以来，我一直在努力研究一种算法。

输入:

• 3 个字符串列表:L1、L2 和 L3
• 包含 3 个列表中的两个索引的 3 个对列表:P12、P13、P23

输出:包含根据对列表分组的所有字符串的一个列表。 结果的顺序无关紧要。

一个例子:

L1 = ["toto", "tata"]
L2 = ["tutu", "vincent"]
L3 = ["georges", "Jean-Eude", "Pikachu"]
P12 = [(0,1)]
P13 = [(0,1)]
P23 = [(1,0),(1,1)]
algorithm()
S = ["toto vincent georges Jean-Eude", "tata", "tutu", "Pikachu"]

解释:

P12 "toto"和 "vincent"被分组

P13 "toto"et "Jean-Eude"必须分组，但因为 "toto"和 "vincent"已经分组，所以是 "toto vincent Jean-Eude"

对于 P23:(1,0) "georges"与其他 3 个分组(1,1) 没有变化

另一个例子

T1 = ["toto", "tata"]
T2 = ["tutu"]
T3 = ["georges"]
P12 = [(1,0)]
P13 = [(0,0)]
P23 = [(0,0)]
Output = ["Toto tata tutu georges"]

谢谢

Answer 1

我会将其视为连通分量图问题。

from collections import deque # bfs

def bfs(adj_l, i, comp):
    """Performs a Breadth First Search from node i on the graph given by adjacency list, filling the components list
. Returns the nodes of the component."""

    l=[i]
    queue = deque([i])
    comp[i] = i
    while queue:
        j = queue.popleft()
        for neighbor in adj_l[j]:
            if comp[neighbor] is None:
                queue.append(neighbor)
                comp[neighbor] = i # update the component
                l.append(neighbor)
    return l

def connectedcomponents(adj_l):
    """Returns the connected components (list of list of nodes) for the graph given by adjency list."""

    n = len(adj_l)

    comp = [None]*n
    ll=[]
    for i in range(n):
        if comp[i] is None:
            ll.append(bfs(adj_l, i, comp))

    return ll

def graph_operations(L1, L2, L3, P12, P13, P23):
    l=L1+L2+L3
    v=[[] for _ in l]
    for i,j in P12:
        v[i].append(j+len(L1))
        v[j+len(L1)].append(i)
    for i,j in P13:
        v[i].append(j+len(L1)+len(L2))
        v[j+len(L1)+len(L2)].append(i)
    for i,j in P23:
        v[i+len(L1)].append(j+len(L1)+len(L2))
        v[j+len(L1)+len(L2)].append(i+len(L1))

    ll = connectedcomponents(v)

    ll = [[l[i] for i in li] for li in ll]

    return ll

L1 = ["toto", "tata"]
L2 = ["tutu", "vincent"]
L3 = ["georges", "Jean-Eude", "Pikachu"]
P12 = [(0,1)]
P13 = [(0,1)]
P23 = [(1,0),(1,1)]

print graph_operations(L1, L2, L3, P12, P13, P23)

L1 = ["toto", "tata"]
L2 = ["tutu"]
L3 = ["georges"]
P12 = [(1,0)]
P13 = [(0,0)]
P23 = [(0,0)]

print graph_operations(L1, L2, L3, P12, P13, P23)

复杂度是线性的。