Полиномиальное поколение степени n

Question

Я в основном ищу функцию суммирования, которая будет вычислять многочлены с учетом числа переменных и степени.

Пример

2 Variables; 2 Degrees:

x^2+y^2+x*y+x+y+1

Спасибо.

Answer 1

См. Кнут Искусство компьютерного программирования , Vol. 4, сборник 3 для исчерпывающего ответа.

Краткий ответ: достаточно сгенерировать все полиномиальные выражения в n переменных со степенью точно d. Затем для вашей задачи вы можете либо собрать ответы с градусами ≤d, либо добавить фиктивную переменную «1».

Таким образом, задача генерации всех выражений со степенью точно d представляет собой простую задачу генерации всех упорядоченных разбиений (т. Е. Всех неотрицательных целочисленных решений x ₁ + ... + x _n = d), и это можно сделать с помощью простого алгоритма возврата. («Поиск в глубину»)

Answer 2

Учитывая N переменных и максимальную степень D, у вас есть массив из D слотов для заполнения всеми возможными комбинациями переменных.

[_, _, ..., _, _]

Вам разрешено заполнять слоты любой из N переменных на любое число <= D общее количество раз. Поскольку умножение коммутативно, достаточно не заботиться о порядке переменных. Таким образом, эта проблема сводится к генерации (1) разделов целого числа и (2) подмножеств набора. </p>

Надеюсь, это как минимум начало вашего решения.

Answer 3

Похоже, это также вариант динамического программирования для задачи о ранце 0-1. Здесь нас будут интересовать все возможные листы дерева решений.