带容量限制的嵌套列表元素合并实现技术问询

目标嵌套列表 #

[[[0.0, 2.0], [6.0, 20.0]],
 [[0.0, 5.0], [6.0, 12.0]],
 [[2.0, 5.0], [20.0, 12.0]],
 [[3.0, 4.0], [12.0, 6.0]],
 [[0.0, 1.0], [6.0, 6.0]],
 [[2.0, 3.0], [20.0, 12.0]],
 [[0.0, 3.0], [6.0, 12.0]]]

合并约束规则 #

• 容量约束：每个地址对应待收集箱子数由子列表的第二个元素给出，合并后总容量不得超过设定值（示例为40）。例如[[0.0,2.0],[6.0,20.0]]中，地址0和2的箱子数分别为6和20，总容量为26。
• 合并位置约束：仅当待合并的地址处于已合并列表的首尾位置时，才可执行合并操作。

合并流程与最终结果 #

分步处理说明 #

• 处理元素[[0.0,5.0],[6.0,12.0]]：地址0在已合并列表[0.0,2.0]的开头，将地址5添加至0的前方，得到新合并列表[[5.0,0.0,2.0],[12.0,6.0,20.0]]，总容量38，符合要求。
• 处理元素[[2.0,5.0],[20.0,12.0]]：地址2和5已在同一合并列表，跳过。
• 处理元素[[3.0,4.0],[12.0,6.0]]：地址3和4均为新地址，作为新合并组保留。
• 处理元素[[0.0,1.0],[6.0,6.0]]：地址0处于合并列表中间位置，无法添加地址1，将1放入未合并列表。
• 处理元素[[2.0,3.0],[20.0,12.0]]：地址2和3分别在两个合并组，合并后总容量超过40，跳过。
• 处理元素[[0.0,3.0],[6.0,12.0]]：地址0处于合并列表中间位置，无法合并，跳过。

最终结果 #

• 合并列表1：[[5.0,0.0,2.0],[12.0,6.0,20.0]]
• 合并列表2：[[3.0,4.0],[12.0,6.0]]
• 未合并地址：{1.0}

现有基础代码（无容量约束） #

pairs3 = [[0, 2], [0, 5], [2, 5], [3, 4], [0, 1], [2, 3], [0, 3], [2, 6], [1, 2]]

done_ind = []
done_merged = []
done_ind.extend(pairs3[0])
done_merged.append(pairs3[0])
all_points = []
for i in pairs3:
    all_points.extend(i)
all_points = set(all_points)
for i in range(1,len(pairs3)):
    print(done_merged)
    total = 0
    total_n = []
    for t in pairs3[i]:
        if t in done_ind:
            total+=1
            total_n.append(t)
    if total == 0:
        done_ind.extend(pairs3[i])
        done_merged.append(pairs3[i])
        print(done_ind)
    elif total == 1:
        total_n = total_n[0]
        for y in range(len(done_merged)):
            if total_n in done_merged[y]:
                indexx = done_merged[y].index(total_n)
                insert_point = list(set(pairs3[i])-set([total_n]))
                insert_point = insert_point[0]
                if indexx == 0:
                    done_merged[y].insert(indexx,insert_point)
                    done_ind.append(insert_point) 
                elif indexx == len(done_merged[y])-1:
                    done_merged[y].insert(indexx+1,insert_point)
                    done_ind.append(insert_point) 
        print(done_ind)
    elif total == 2:
        print("try to merge two lists if values to be merged are on the outside")
print("points not merged:", all_points - set(done_ind))

完善后的代码（满足双约束） #

# 目标嵌套列表
target_list = [[[0.0, 2.0], [6.0, 20.0]],
               [[0.0, 5.0], [6.0, 12.0]],
               [[2.0, 5.0], [20.0, 12.0]],
               [[3.0, 4.0], [12.0, 6.0]],
               [[0.0, 1.0], [6.0, 6.0]],
               [[2.0, 3.0], [20.0, 12.0]],
               [[0.0, 3.0], [6.0, 12.0]]]

# 容量上限设定
CAPACITY_LIMIT = 40

# 初始化合并组：每个合并组存储[地址列表, 容量列表, 总容量]
merged_groups = []
first_item = target_list[0]
addr_list = first_item[0]
cap_list = first_item[1]
total_cap = sum(cap_list)
merged_groups.append([addr_list, cap_list, total_cap])

# 收集所有地址
all_addrs = set()
for item in target_list:
    all_addrs.update(item[0])

# 遍历剩余元素处理
for item in target_list[1:]:
    current_addrs = item[0]
    current_caps = item[1]
    # 建立地址到对应容量的映射
    addr_to_cap = dict(zip(current_addrs, current_caps))
    
    # 统计当前元素中已有多少地址在合并组中
    existing_count = 0
    existing_info = []  # 存储(所在组索引, 地址在组内的位置, 地址)
    for idx, group in enumerate(merged_groups):
        group_addrs = group[0]
        for addr in current_addrs:
            if addr in group_addrs:
                pos = group_addrs.index(addr)
                existing_info.append((idx, pos, addr))
                existing_count += 1
    
    if existing_count == 0:
        # 两个地址都是新的，直接作为新组添加
        new_total = sum(current_caps)
        if new_total <= CAPACITY_LIMIT:
            merged_groups.append([current_addrs.copy(), current_caps.copy(), new_total])
    elif existing_count == 1:
        # 只有一个地址在已合并组中，检查位置是否在首尾
        group_idx, pos, existing_addr = existing_info[0]
        group = merged_groups[group_idx]
        # 获取待添加的地址和对应容量
        new_addr = [addr for addr in current_addrs if addr != existing_addr][0]
        new_cap = addr_to_cap[new_addr]
        
        # 检查位置是否符合约束，且合并后容量不超限
        if (pos == 0 or pos == len(group[0]) - 1) and (group[2] + new_cap) <= CAPACITY_LIMIT:
            if pos == 0:
                # 添加到开头
                group[0].insert(0, new_addr)
                group[1].insert(0, new_cap)
            else:
                # 添加到末尾
                group[0].append(new_addr)
                group[1].append(new_cap)
            # 更新总容量
            group[2] += new_cap
    elif existing_count == 2:
        # 两个地址都已存在，分两种情况：同组或不同组
        info1, info2 = existing_info
        if info1[0] == info2[0]:
            # 同组，跳过
            continue
        else:
            # 不同组，检查两个地址是否都在各自组的首尾
            group1 = merged_groups[info1[0]]
            pos1 = info1[1]
            group2 = merged_groups[info2[0]]
            pos2 = info2[1]
            
            # 检查位置是否符合合并条件，且合并后总容量不超限
            valid_pos1 = pos1 == 0 or pos1 == len(group1[0]) - 1
            valid_pos2 = pos2 == 0 or pos2 == len(group2[0]) - 1
            total_after_merge = group1[2] + group2[2]
            
            if valid_pos1 and valid_pos2 and total_after_merge <= CAPACITY_LIMIT:
                # 合并两个组：根据位置决定拼接顺序
                if pos1 == len(group1[0]) - 1 and pos2 == 0:
                    # group1末尾接group2开头
                    group1[0].extend(group2[0])
                    group1[1].extend(group2[1])
                elif pos1 == 0 and pos2 == len(group2[0]) - 1:
                    # group2末尾接group1开头
                    group1[0] = group2[0] + group1[0]
                    group1[1] = group2[1] + group1[1]
                elif pos1 == len(group1[0]) - 1 and pos2 == len(group2[0]) - 1:
                    # group1末尾接group2反转
                    group1[0].extend(reversed(group2[0]))
                    group1[1].extend(reversed(group2[1]))
                elif pos1 == 0 and pos2 == 0:
                    # group2反转后接group1开头
                    group1[0] = list(reversed(group2[0])) + group1[0]
                    group1[1] = list(reversed(group2[1])) + group1[1]
                # 更新总容量
                group1[2] = total_after_merge
                # 删除被合并的组
                del merged_groups[info2[0]]

# 整理输出结果
print("最终合并列表：")
for group in merged_groups:
    print(f"[{group[0]}, {group[1]}]")

# 计算未合并地址
merged_addrs = set()
for group in merged_groups:
    merged_addrs.update(group[0])
unmerged_addrs = all_addrs - merged_addrs
print(f"\n未合并地址：{unmerged_addrs}")

代码关键说明 #

1. 合并组结构：每个合并组存储[地址列表, 容量列表, 总容量]，方便快速计算和更新总容量。
2. 容量校验：每次合并前都会检查合并后的总容量是否超过设定上限。
3. 位置约束校验：仅当待合并地址处于组的首尾位置时，才允许执行合并操作。
4. 跨组合并处理：当两个地址分别在不同组时，会根据位置判断拼接顺序，确保符合位置约束。

内容的提问来源于stack exchange，提问作者Jordi van Selm