Python实现指定长度区间内固定顺序子区间的所有可行排列枚举

给定长度为L的区间，以及三个固定长度的子项（顺序固定为a→b→c），需要枚举所有可行的放置组合，未被子项占据的位置用0填充。例如当L=10，子项a、b、c的长度分别为4、3、1时，共有10种可行放置方式。

可行放置的条件分析 #

三个子项的总长度为sum_len = len(a) + len(b) + len(c)：

• 若sum_len > L：没有可行放置方式，直接返回空列表。
• 若sum_len ≤ L：剩余空隙长度为gap = L - sum_len，这些空隙需要分配到四个区域：a之前、a与b之间、b与c之间、c之后。我们需要枚举所有非负整数组合(x, y, z, w)，满足x + y + z + w = gap，其中：
  • x：a之前的0的数量
  • y：a与b之间的0的数量
  • z：b与c之间的0的数量
  • w：c之后的0的数量

Python实现代码 #

基础版本（按长度生成子项标记）

该版本直接根据子项长度生成标记序列（用1、2、3区分三个子项）：

def generate_placements(L, len_a, len_b, len_c):
    total_length = len_a + len_b + len_c
    if total_length > L:
        return []
    
    gap = L - total_length
    placements = []
    
    # 枚举所有空隙分配组合
    for x in range(gap + 1):
        remaining_after_x = gap - x
        for y in range(remaining_after_x + 1):
            remaining_after_y = remaining_after_x - y
            for z in range(remaining_after_y + 1):
                w = remaining_after_y - z
                # 构造放置序列
                sequence = (
                    [0] * x
                    + [1] * len_a
                    + [0] * y
                    + [2] * len_b
                    + [0] * z
                    + [3] * len_c
                    + [0] * w
                )
                placements.append(sequence)
    
    return placements

# 测试示例
if __name__ == "__main__":
    L = 10
    a_len, b_len, c_len = 4, 3, 1
    results = generate_placements(L, a_len, b_len, c_len)
    print(f"总可行放置数：{len(results)}")
    for idx, seq in enumerate(results, 1):
        print(f"第{idx}种：{seq}")

灵活版本（支持自定义子项内容）

如果需要使用自定义的子项内容（而非长度标记），可以修改为以下版本：

def generate_placements(L, a, b, c):
    len_a, len_b, len_c = len(a), len(b), len(c)
    total_length = len_a + len_b + len_c
    if total_length > L:
        return []
    
    gap = L - total_length
    placements = []
    
    for x in range(gap + 1):
        remaining_after_x = gap - x
        for y in range(remaining_after_x + 1):
            remaining_after_y = remaining_after_x - y
            for z in range(remaining_after_y + 1):
                w = remaining_after_y - z
                sequence = (
                    [0] * x
                    + list(a)
                    + [0] * y
                    + list(b)
                    + [0] * z
                    + list(c)
                    + [0] * w
                )
                placements.append(sequence)
    
    return placements

# 测试自定义子项
if __name__ == "__main__":
    L = 10
    custom_a = [5, 5, 5, 5]
    custom_b = [7, 7, 7]
    custom_c = [9]
    results = generate_placements(L, custom_a, custom_b, custom_c)
    print(f"总可行放置数：{len(results)}")
    for idx, seq in enumerate(results, 1):
        print(f"第{idx}种：{seq}")

代码说明 #

• 三层循环遍历所有合法的空隙分配组合，确保每个区域的空隙数非负且总和等于gap。
• 序列构造通过拼接空隙0和子项内容实现，保证子项顺序固定。
• 测试部分验证了题目中的示例，输出结果与描述一致（10种可行方式）。

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