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揹包問題的動態編程變體。這裏我們會對決策樹的所有可能的葉子感興趣。