如何用Python高效计算初等对称多项式（ESPs）？

需求说明 #

需要实现一个计算初等对称多项式（ESPs）的Python函数，满足：

• 输入：非空数值列表x
• 输出：包含所有对应ESPs结果的列表，按约定第0项恒为1。例如输入[x1, x2, x3]，输出为[1, x1+x2+x3, x1x2+x1x3+x2x3, x1x2x3]

初始方案的局限性 #

最初使用itertools.combinations遍历所有k元组（k从1到列表长度）计算，时间复杂度为O(n·2ⁿ)（n为列表长度），属于指数级，面对较大规模输入时性能极差，扩展性不足。

优化方案：基于牛顿恒等式的O(n²)实现 #

牛顿恒等式建立了初等对称多项式与幂和之间的关联，能将计算复杂度降至二次方，完全满足性能需求。

实现代码 #

def evaluate_all_ESPs(x: list) -> list:
    """
    计算给定数值列表对应的所有初等对称多项式（ESPs），返回包含len(x)+1个结果的列表

    若将结果记为e[k]（0 ≤ k ≤ len(x)），则：
        • e[0] = 1（约定）
        • 对于1 ≤ k ≤ len(x)，e[k]是所有k个元素乘积的和：
            - e[1] = x[0] + x[1] + ... + x[-1]（所有元素的和）
            - e[2] = x[0]*x[1] + x[0]*x[2] + ... + x[-2]*x[-1]（所有二元乘积的和）
            - ...
            - e[len(x)] = x[0]*x[1]*...*x[-1]（所有元素的乘积）

    注意：本函数使用牛顿恒等式计算，比遍历所有k元组的方法高效得多，算法复杂度为O(len(x)²)
    """
    # 输入检查
    if not isinstance(x, list):
        raise TypeError(f"\n\n预期输入为列表，但实际收到类型 '{type(x).__name__}' : '{x}'\n")
    if len(x) == 0:
        raise ValueError("\n\n输入不能为空列表！\n")

    # 初始化变量
    nb_elements = len(x)
    evaluations = [1] + [0] * nb_elements  # 对应文档中的e列表
    powers_of_x = [1] * nb_elements        # 存储每个元素的i次幂
    sums_of_powers_of_x = [0] * nb_elements# 存储所有元素i次幂的和

    for i in range(nb_elements):
        # 更新元素的幂次及幂和
        powers_of_x = [x_k * prev_pow for x_k, prev_pow in zip(x, powers_of_x)]
        sums_of_powers_of_x[i] = sum(powers_of_x)

        # 应用牛顿恒等式计算当前对称多项式
        current_eval = 0
        sign = 1
        for j in range(i, -1, -1):
            current_eval += sign * evaluations[j] * sums_of_powers_of_x[i - j]
            sign *= -1
        # 根据结果类型选择整数或浮点数除法
        current_eval = current_eval // (i + 1) if isinstance(current_eval, int) else current_eval / (i + 1)

        # 更新结果列表
        evaluations[i + 1] = current_eval

    return evaluations

调研情况说明 #

在寻找解决方案时，未在Stack Overflow找到直接可用的代码（仅Math Stack Exchange有相关算法提及），同时调研了以下资源：

• pySymmPol包：仅支持多项式符号运算，无法处理数值求值需求
• 一篇浮点输入下快速ESPs计算的论文：作者未提供代码，且算法实现难度高（作者采用C语言实现）

目前网上缺乏基于牛顿恒等式计算ESPs的明确Python实现，希望这个代码能为有相同需求的开发者节省时间。

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