获取共享公共元素的子列表组，但这些元素在所有子列表中并不相同

Question

我必须使用 python 将子列表与集合“p”中的公共元素进行分组。 p 元素并不总是位于子列表的第 1 或 las 位置。分组（结果）列表是列表 r。

结果列表 r 是根据初始列表 l 构建的。 r 中的第一个子列表必须包含起点 start 以及由列表 p 中的元素连接的中间子列表。 r 中的最后一个子列表必须包含结束点 end。 这是一个小例子。

#starting point
start = 1

#ending point
end = 9

 #items to be used to link "start" and "end" points.
p = [2, 4, 5]

#complete nested list
l = [
    [0, 7],
    [1, 2],
    [8, 15, 19, 20],
    [0, 6],
    [2, 3, 5],
    [10, 14],
    [5, 8, 4, 3],
    [4, 9, 6],
    [14, 21],
    [20, 9]
]

#result list, with "start" in sublist 0, "end" in sublist 3.
r = [
    [1, 2],
#----^
    [2, 3, 5],
    [5, 8, 4, 3],
    [4, 9, 6]
#-------^
]

这是我尝试用来获取列表 r 的代码。

#get routes with "start" element
ok_routes=[]
for i in range(len(l)):
       if start in l[i]:
        ok_routes.append((l[i]))



#get routes with "end" element
dk_routes=[]
for i in range(len(l)):
       if end in l[i]:
        dk_routes.append((l[i]))


#start r, appending "start" element
r_temp=[]
for i in range(len(ok_routes)):
    
    r_temp.append([ok_routes[i]])
    


#Using shuffle to generate al possible combinations of sublists
a_shuffle = copy.deepcopy(l) 
random.shuffle(a_shuffle)


#generate r using intersection of sets.
r=[]
for i in range(0,len(r_temp)):   
    for j in range(0,len(a_shuffle)):
        if set(p).intersection(a_shuffle[j]):
            r.append(a_shuffle[j])
    break

#r=[[2, 3, 5], [1, 2], [4, 9, 6], [5, 8, 4, 3]]

此代码有时有效，有时无效。 对于更多带有“开始”和“结束”点的子列表，“r”无效，因为子列表不会与 p 中的元素完全“相交”，例如：如果子列表 [2, 8] 添加后，我得到了这个解决方案，

r = [[5, 8, 4, 3], [2, 8],[2, 3, 5], [1, 2], [4, 9, 6]]

这个解决方案是无效的，因为不能考虑子列表 [2,8]，因为“8”不是起点或终点。

提前致谢。

Answer 1

使用图遍历算法。将每个子列表视为图中的一个节点，如果两个节点共享集合

p

中的公共元素，则它们之间存在一条边。然后就可以使用DSF算法来查找从起始节点到结束节点的所有路径：

from collections import defaultdict
graph = defaultdict(list)
for i, sublist in enumerate(l):
    for j, other_sublist in enumerate(l):
        if i != j and any(elem in sublist for elem in p):
            graph[i].append(j)
start_node = next(i for i, sublist in enumerate(l) if start in sublist)
end_node = next(i for i, sublist in enumerate(l) if end in sublist)
def dfs(node, path):
    if node == end_node:
        result.append(path)
    else:
        for neighbor in graph[node]:
            if neighbor not in path:
                dfs(neighbor, path + [neighbor])
result = []
dfs(start_node, [start_node])
r = [[l[node] for node in path] for path in result]
print(r)