Generate all possible curve sequences for all possible road length.

main.py

def road_length_to_all_possible_curve_sequences(curve_length_by_type: list[int], max_road_length):
    '''对每种道路长度，生成可能的曲线组合序列。

    Args:
        curve_length_by_type (list[int], optional): 每种类型曲线的长度。
        max_road_length (int): 最大道路长度。
    Returns:
        road_length_to_last_possible_curve_type_list (dict[int, list[int]]):每种长度的道路最后一段曲线的类型。
    '''
    # curve_length_by_type[curve_type_index] = curve_length
    # 记录了每种类型曲线的长度
    curve_type_count = len(curve_length_by_type)

    # road_length_to_last_possible_curve_type_list[road_length] = [curve_type_index, ...]
    # 一条道路由多段曲线连接组成，这个字典记录了每种长度的道路最后一段曲线的类型
    road_length_to_last_possible_curve_type_list: dict[int, list[int]] = {}

    # 所有可能的道路长度，按照从小到大排序
    road_length_list: list[int] = []
    import bisect
    
    # 需要填充 road_length_to_last_possible_curve_type_list，它包含了不超过 max_road_length 长度的所有长度的道路最后一段曲线的类型
    current_road_length = 0
    current_length_index = -1
    while current_road_length < max_road_length:
        # 从 current_road_length 开始，尝试用所有的 curve type 延长这条道路
        # print('current_road_length', current_road_length)
        for curve_type_index in range(curve_type_count):
            next_road_length = current_road_length + curve_length_by_type[curve_type_index]
            if next_road_length <= max_road_length:
                # 将延长的结果记录到 road_length_to_last_possible_curve_type_list
                if next_road_length not in road_length_to_last_possible_curve_type_list:
                    road_length_to_last_possible_curve_type_list[next_road_length] = [curve_type_index]
                    bisect.insort(road_length_list, next_road_length)
                else:
                    road_length_to_last_possible_curve_type_list[next_road_length].append(curve_type_index)
        # print('road_length_to_last_possible_curve_type_list', road_length_to_last_possible_curve_type_list)
        current_length_index += 1
        if current_length_index >= len(road_length_list):
            break
        current_road_length = road_length_list[current_length_index]

    return road_length_to_last_possible_curve_type_list


if __name__ == '__main__':
    curve_length_by_type = [70, 75, 140, 270]
    road_length_to_last_possible_curve_type_list = road_length_to_all_possible_curve_sequences(curve_length_by_type, 300)
    road_length_list = sorted(road_length_to_last_possible_curve_type_list.keys())

    def print_possible_curve_sequences(road_length: int, curve_sequence: list[int]):
        if road_length == 0:
            print('  ', curve_sequence)
            return
        for curve_type_index in road_length_to_last_possible_curve_type_list[road_length]:
            print_possible_curve_sequences(road_length - curve_length_by_type[curve_type_index], curve_sequence + [curve_type_index])

    # 对 road_length_list 中的每个长度，打印出所有可能的曲线组合序列
    for road_length in road_length_list:
        print(f'road_length {road_length} possible curve seqences:')
        print_possible_curve_sequences(road_length, [])