Python中生成列表元素两两绑定相加所有可能形式的高效实现

给定一个Python列表，需要生成所有满足规则的加法表达式字符串，具体规则如下：

• 表达式必须完整使用列表内所有元素，不能遗漏、重复元素，允许元素的任意排列
• 所有加法绑定严格遵循“每次取两个元素相加”的要求：任意一次加法的两个操作数，要么是原始列表的单个元素，要么是已经完成绑定的两个元素的和，禁止出现三个元素直接连写无括号的情况
• 列表长度为奇数时，允许存在1个未被配对的单元素游离项，其余元素必须全部两两绑定；列表长度为偶数时，所有元素都必须两两绑定，无游离项

短列表示例效果：当输入为mylist = [1, 2, 3]时，合法输出示例为：

• (1 + 2) + 3
• 1 + (2 + 3)
• (1 + 3) + 2
• 1 + (3 + 2)

长列表示例效果：当输入为mylist = [1, 2, 3, 4, 5]时，合法输出示例包括：

• 1 + (2 + 3) + (4 + 5)
• (1 + 2) + 3 + (4 + 5)
• (1 + 2) + (3 + 4) + 5

尝试用itertools内置方法开发时，已经可以通过itertools.permutations拿到所有元素的全排列，现有测试代码为：

import itertools
stuff = [1, 2, 3]
for per in itertools.permutations(stuff):
    print(per)

但后续开发环节存在无法推进的问题：

• 拿到元素全排列后，如何穷举所有合法的两两拆分分组方式
• 列表长度为奇数、存在单个未配对元素时，如何调整分组逻辑才能覆盖所有合法场景
• 如何保证实现方法的运行效率，适配更长的输入列表

整个实现可以拆成两个独立环节，整体效率和问题本身的输出量级匹配，没有冗余计算：

1. 全排列生成环节
   直接使用itertools.permutations拿到所有不重复的元素排列即可，这部分的时间复杂度为O(n!)，是排列类问题的理论最低复杂度，没有可优化空间。
2. 分组结构生成环节
   采用递归方式生成所有合法的两两绑定结构，逻辑天然适配奇数长度的列表：
   • 递归终止条件：当待处理的序列长度为1时，直接返回该元素的字符串形式
   • 递归逻辑：遍历序列中所有相邻的两个元素，将这两个元素用括号包裹绑定为一个新的“虚拟元素”，再和序列剩余元素组成新序列，递归生成所有可能的组合
   • 结果优化：用集合存储生成的表达式，自动去重，避免重复输出

需要注意的是，这类两两绑定的括号结构的总数量本身由卡塔兰数决定，随列表长度增长会快速膨胀，不存在可以跳过这个输出量级的高效生成方法，上述递归实现已经是Python环境下可达成的最优效率方案。

可直接运行的完整实现代码：

import itertools

def generate_all_groupings(sequence):
    # 递归生成序列对应的所有两两绑定表达式
    if len(sequence) == 1:
        return [str(sequence[0])]
    result = set()
    seq_len = len(sequence)
    for idx in range(seq_len - 1):
        # 绑定相邻两个元素为一个组
        bind_group = f"({sequence[idx]} + {sequence[idx+1]})"
        # 生成绑定后的新序列
        new_sequence = list(sequence[:idx]) + [bind_group] + list(sequence[idx+2:])
        # 递归生成新序列的所有分组形式
        for sub_expr in generate_all_groupings(new_sequence):
            result.add(sub_expr)
    return list(result)

def generate_all_expressions(input_list):
    all_expressions = []
    # 遍历所有元素排列
    for perm in itertools.permutations(input_list):
        all_expressions.extend(generate_all_groupings(perm))
    # 全局去重后返回
    return list(set(all_expressions))

# 测试用例
if __name__ == "__main__":
    mylist = [1, 2, 3]
    for expr in generate_all_expressions(mylist):
        print(expr)

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