Есть ли простой и эффективный способ оценки элементарных симметричных полиномов в Python? ⇐ Python

[Anonymous]

В настоящее время я работаю над проектом, который включает в себя оценку элементарных симметричных полиномов (или «ESP») с использованием Python. По сути, мне нужно создать функцию, которая:

• принимает непустой список x (числовых значений) в качестве входных данных
• выводит список, содержащий все соответствующие оценки ESP, где каждый ESP находится в переменных len(x) (также по соглашению мы могли бы сказать, что «0-й» ESP всегда равен 1) >

Например, если мой входной список — x = [x1, x2, x3], то я хочу, чтобы функция выводила список [1, x1 + x2 + x3, x1 * x2 + x1 * x3 + x2 * x3, x1 * x2 * x3].
Изначально я написал функция, которая перебирала все кортежи из k (для всех целых чисел k в диапазоне [1, len(x)]), используя метод «itertools.combinations», но, очевидно, это не так. хорошо масштабироваться, поскольку временная сложность моей функции была экспоненциальной: она была в O(len(x) * 2^len(x)). Поэтому мне было интересно, существует ли какой-нибудь алгоритм, который мог бы выполнить ту же работу, но за полиномиальное время (скажем, с квадратичной или кубической временной сложностью).
Затем я наткнулся на тождества Ньютона (связывающие ESP с суммами степеней), и они выполняют свою работу с кубической временной сложностью ! Для моих целей на этот раз сложности достаточно, но есть ли более эффективный способ оценки ESP? После некоторых исследований я не видел ни одного сообщения о переполнении стека с явным код для решения моей проблемы (хотя в этом сообщении Math Stack Exchange упоминаются некоторые алгоритмы). Я также просмотрел следующие ресурсы:

• Пакет pySymmPol (и соответствующая статья): он выглядел многообещающе, но на самом деле он не поддерживает полиномиальную оценку. ...
• Эта статья, описывающая быстрый алгоритм оценки ESP (с входными данными с плавающей запятой): к сожалению, похоже, что авторы не предоставляют никакого кода, а их алгоритмы кажутся очень утомительно для реализации (также я думаю, что они сказали, что их код был написан на C)

Кроме того, вот улучшенная функция, которую я реализовал для решения моей первоначальной проблемы, используя тождества Ньютона:

Код: Выделить всё

def evaluate_all_ESPs(x: list) -> list:
"""
This function evaluates all the Elementary Symmetric Polynomials (or
"ESPs") in `len(x)` variables on the given input list of numeric values,
and returns the corresponding `len(x) + 1` evaluations in a list

If we label these evaluated ESPs as `e[k]` (where `0 

Подробнее здесь: [url]https://stackoverflow.com/questions/78999933/is-there-a-simple-and-efficient-way-to-evaluate-elementary-symmetric-polynomials[/url]