Есть ли простой и эффективный способ оценки элементарных симметричных полиномов в 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]