如何用Python解决生成指定阶数多项式项的组合问题

这个问题本质是求解不定方程 e1 + e2 + ... + en = order 的所有非负整数解，其中n是变量列表长度，每个解对应一个多项式项的指数组合，将指数组合格式化后即可得到最终结果。

实现1：递归实现（无第三方依赖） #

递归思路：

• 每一步处理一个变量，给它分配0到剩余可用阶数的指数
• 剩余阶数减去当前分配的指数后，交给下一个变量处理
• 所有变量处理完成时，若剩余阶数刚好为0，就将当前指数组合转换为多项式项加入结果集

def generate_poly_terms(variables: list[str], order: int) -> list[str]:
    var_count = len(variables)
    result = []

    def backtrack(current_var_idx: int, left_order: int, exponent_list: list[int]):
        # 所有变量处理完成
        if current_var_idx == var_count:
            if left_order == 0:
                # 指数组合转多项式项
                term_parts = []
                for var, exp in zip(variables, exponent_list):
                    if exp == 0:
                        continue
                    term_parts.append(var if exp == 1 else f"{var}^{exp}")
                result.append("*".join(term_parts))
            return
        # 当前变量可分配0到剩余阶数的指数
        # 若要匹配示例输出顺序，把range(left_order + 1)改为range(left_order, -1, -1)即可
        for e in range(left_order + 1):
            backtrack(current_var_idx + 1, left_order - e, exponent_list + [e])
    
    backtrack(0, order, [])
    return result

测试用例：

print(generate_poly_terms(["x1", "x2", "x3"], 2))
# 调整遍历顺序后输出：['x1^2', 'x1*x2', 'x1*x3', 'x2^2', 'x2*x3', 'x3^2']
print(generate_poly_terms(["x1", "x2"], 3))
# 调整遍历顺序后输出：['x1^3', 'x1^2*x2', 'x1*x2^2', 'x2^3']

实现2：基于星棒法的标准库实现（更简洁） #

基于组合数学的「星与棒」定理，直接用Python标准库itertools.combinations生成所有指数组合，不需要手写递归逻辑：

from itertools import combinations

def generate_poly_terms(variables: list[str], order: int) -> list[str]:
    var_count = len(variables)
    result = []
    # 星棒法：在order个星之间插入var_count-1个隔板，拆分得到所有指数组合
    for split_points in combinations(range(order + var_count - 1), var_count - 1):
        exponent_list = []
        prev_point = -1
        for p in split_points:
            exponent_list.append(p - prev_point - 1)
            prev_point = p
        exponent_list.append(order + var_count - 1 - prev_point - 1)
        # 指数组合转多项式项
        term_parts = []
        for var, exp in zip(variables, exponent_list):
            if exp == 0:
                continue
            term_parts.append(var if exp == 1 else f"{var}^{exp}")
        result.append("*".join(term_parts))
    return result

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