Python实现基于集合p的子列表分组：衔接起点与终点

需使用Python对嵌套列表l中的子列表进行分组，分组规则为子列表间通过集合p中的元素相连，结果列表r需以包含起点start的子列表开头，以包含终点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]
#-------^
]

现有尝试代码 #

# 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 all 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]]

存在的问题 #

• 当前代码结果不稳定，有时有效有时无效；
• 当新增如[2,8]这类子列表时，结果会混入无效项（因8非起点或终点）。

要解决这个问题，需要构建从起点子列表到终点子列表的连通路径，而非随机筛选。核心思路是：

1. 筛选出所有包含start的起始子列表和包含end的终止子列表；
2. 以起始子列表为起点，通过p中的元素逐步扩展连通的子列表，直到找到包含end的子列表；
3. 确保路径中相邻子列表通过p元素相连，且无重复子列表。

实现代码 #

import copy

def find_connected_path(start, end, p, nested_list):
    p_set = set(p)
    # 筛选起始和终止子列表
    start_sublists = [sublist for sublist in nested_list if start in sublist]
    end_sublists = [sublist for sublist in nested_list if end in sublist]
    
    if not start_sublists or not end_sublists:
        return []  # 无起点或终点子列表，返回空
    
    # 遍历所有起始子列表，寻找有效路径
    for start_sub in start_sublists:
        visited = set()
        path = [start_sub]
        visited.add(tuple(start_sub))  # 用tuple存储子列表（list不可哈希）
        
        current_elements = set(start_sub) & p_set
        if not current_elements:
            continue  # 起始子列表与p无交集，无法连通
        
        while True:
            found = False
            # 遍历未访问的子列表，寻找与当前路径尾部连通的项
            for sublist in nested_list:
                sub_tuple = tuple(sublist)
                if sub_tuple in visited:
                    continue
                # 检查子列表是否与p有交集，且和路径尾部通过p元素相连
                sub_intersect = set(sublist) & p_set
                if sub_intersect and (sub_intersect & current_elements):
                    path.append(sublist)
                    visited.add(sub_tuple)
                    current_elements = sub_intersect
                    found = True
                    # 到达终点则返回路径
                    if end in sublist:
                        return path
                    break
            if not found:
                break  # 无法扩展路径，尝试下一个起始子列表
    
    return []  # 未找到有效路径

# 测试示例
start = 1
end = 9
p = [2, 4, 5]
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]
]

r = find_connected_path(start, end, p, l)
print(r)
# 输出: [[1, 2], [2, 3, 5], [5, 8, 4, 3], [4, 9, 6]]

# 测试新增[2,8]的情况
l.append([2,8])
r = find_connected_path(start, end, p, l)
print(r)
# 输出仍为有效路径，不会混入[2,8]

代码说明 #

• 精准筛选：直接过滤出包含起点/终点的子列表，避免无效遍历；
• 连通性校验：每次只选择与当前路径尾部通过p元素相连的子列表，保证路径连续性；
• 去重机制：用visited集合记录已加入路径的子列表，防止循环；
• 终止逻辑：找到包含终点的子列表立即返回，确保结果稳定有效。

内容的提问来源于stack exchange，提问作者Hernan19