如何生成覆盖全部装载点、卡车数≤点数的路线组合算法？

问题背景 #

现有装载点列表x，此前用itertools.permutations生成了所有长度1到len(x)的排列，但现在需要生成所有符合以下规则的路线组合：

• 卡车数量 ≤ 装载点列表长度
• 每个组合覆盖所有装载点，且每个装载点仅出现一次
• 每个卡车对应一条非空的装载点序列（示例如下）

示例输出：

[['1'],['2'],['3'],['4'],['5']]
[['1','2','3','4','5']]
[['1'],['2','3'],['4','5']]
[['1','2','3'],['4','5']]
...

解决方案 #

以下提供两种实现方案，分别对应是否需要考虑卡车路线内的装载点顺序。

方案1：考虑路线内的装载点顺序（模拟实际行驶路线）

如果需要每个卡车的路线是装载点的有序序列（比如先到A再到B和先到B再到A算不同路线），可以用以下代码：

import itertools

def generate_all_truck_routes(x):
    n = len(x)
    all_routes = []
    
    # 遍历所有可能的卡车数量（1到装载点总数）
    for truck_count in range(1, n+1):
        # 生成所有装载点到卡车的分配方式
        for assignment in itertools.product(range(truck_count), repeat=n):
            # 确保每辆卡车至少分配到一个装载点
            if len(set(assignment)) != truck_count:
                continue
            # 按卡车分组装载点
            groups = [[] for _ in range(truck_count)]
            for idx, truck_id in enumerate(assignment):
                groups[truck_id].append(x[idx])
            # 对每个卡车的装载点生成所有可能的行驶顺序排列
            for permuted_groups in itertools.product(*[itertools.permutations(group) for group in groups]):
                # 转换为列表格式
                route = [list(p) for p in permuted_groups]
                all_routes.append(route)
    
    # 可选：去重（避免因卡车ID交换导致的重复组合，若卡车有唯一标识可跳过此步）
    unique_routes = []
    seen = set()
    for route in all_routes:
        # 用排序后的子列表生成唯一标识
        key = tuple(tuple(sorted(sub)) for sub in route)
        if key not in seen:
            seen.add(key)
            unique_routes.append(route)
    
    return unique_routes

# 测试示例
x = ['1','2','3','4','5']
routes = generate_all_truck_routes(x)
# 打印前5个结果
for r in routes[:5]:
    print(r)

代码说明

1. 分配装载点：通过itertools.product生成所有装载点到卡车的分配方案，过滤掉有卡车空载的情况。
2. 生成路线排列：对每个卡车的装载点集合生成所有排列，模拟不同的行驶顺序。
3. 去重处理：可选步骤，用于移除因卡车ID编号不同但实际路线集合相同的重复组合。

方案2：不考虑路线内的顺序（仅需划分装载点）

如果只需要将装载点划分给不同卡车，不关心单辆卡车内部的行驶顺序，可使用简化版本：

import itertools

def generate_all_truck_routes_simple(x):
    n = len(x)
    all_routes = []
    seen = set()
    
    for truck_count in range(1, n+1):
        for assignment in itertools.product(range(truck_count), repeat=n):
            if len(set(assignment)) != truck_count:
                continue
            # 按卡车分组
            groups = [[] for _ in range(truck_count)]
            for idx, truck_id in enumerate(assignment):
                groups[truck_id].append(x[idx])
            # 生成唯一标识去重
            key = tuple(tuple(sorted(sub)) for sub in groups)
            if key not in seen:
                seen.add(key)
                all_routes.append(groups)
    
    return all_routes

# 测试示例
x = ['1','2','3','4','5']
routes = generate_all_truck_routes_simple(x)
for r in routes[:5]:
    print(r)

这个版本生成的结果与你给出的示例完全匹配，仅关注装载点的分组划分，不涉及路线内部的顺序调整。

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