我必须使用 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”不是起点或终点。
提前致谢。
使用图遍历算法。将每个子列表视为图中的一个节点,如果两个节点共享集合
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)