n的多项式生成

Question

我基本上正在寻找一个求和函数，它将根据变量和度数计算多项式。

例

2 Variables; 2 Degrees: 

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

感谢。

Answer 1

给定N个变量，并且最大度数为D，您可以使用D个数组来填充所有可能的变量组合。

[_，_，...，_，_]

你被允许与任何N个变量的任何数量的填充槽总< = d次。由于乘法是可交换的，因此不必考虑变量的排序。因此，这个问题被简化为产生（1）整数的分区和（2）集合的子集。

我希望这至少是您的解决方案的开始。

Answer 2

查看Knuth 计算机编程艺术，Vol。 4，Fascicle 3全面解答。

简答：在n个变量中生成所有多项式表达式，其度数为，正好为 d。然后，针对您的问题，您可以将度数≤d的答案放在一起，或者添加一个虚拟变量“1”。

与度生成所有表达式的问题恰好d是由此产生的所有有序分区（即，所有的非负整数解为x + ... + X _Ñ = d），并且这只是一个可以用简单的回溯算法完成。 （“深度优先搜索”）

Answer 3

这也似乎是0-1背包问题的动态编程变体。这里我们会对决策树的所有可能的叶子感兴趣。