多元多项式的紧密存储系数

Question

安装

我正在编写一段代码，用于处理关于x的d-维度变量的n次多项式，并遇到了其他人可能曾经面临过的问题。这样的多项式可以由对应于x^alpha的系数c(alpha)来表征，其中alpha是一个长度为d的多重指数，指定了必须将d个变量提高到的幂。

维度和阶数完全通用，但在编译时已知，并且可能会很高，例如n = 30和d = 10，尽管可能不会同时出现。这些系数是密集的，意味着大多数系数都是非零的。

指定这样一个多项式所需的系数数量是n + d choose n，在高维中远小于可以填充边长为n的立方体的n^d系数。因此，在我的情况下，我必须将系数存储得相当紧凑。这是有代价的，因为检索给定多重指数alpha的系数需要知道其位置。

问题

是否存在一种（简单直接的）函数，将d维多重指数alpha映射到长度为(n + d) choose n的数组中的位置？

- ANSI C Mastah

---

如果您对我的回答有任何疑问，请告诉我。 - Tom De Caluwé

这很有道理；对我来说现在的问题是，我是否可以利用编译时信息和排序来使用一些模板技巧制作优化代码，或者我是否应该为我遇到的特定情况编写代码生成器。我想这需要一个单独的问题来解决。 - ANSI C Mastah

如果您预先计算二项式系数，索引计算将非常快（需要O(d)时间）。您需要O(d²)的空间来存储二项式系数，实际上是在内存中存储帕斯卡三角形。如果在编译时不知道d，则始终可以即时计算三角形（需要O(d²)时间）。 - Tom De Caluwé

一个人总是可以使用模板来计算三角形；事实上，我已经有这样的代码准备好了，所以唯一阻止我的是需要编写有意义的单元测试。 :) - ANSI C Mastah

Answer 1

组合的排序

一种常见的组合排序方法可以在此维基百科页面中找到。简而言之，您按字典顺序对组合进行排序，因此可以轻松计算较低的组合数。有关说明，请参见组合排序和组合在排序中的位置部分。

预先计算二项式系数将加速索引计算。

将单项式与组合相关联

如果我们现在可以将每个单项式与一个组合相关联，则可以使用上述方法有效地对它们进行排序。由于每个系数都对应着这样一个单项式，因此这将提供您所需要的答案。幸运的是，如果

alpha = (a[1], a[2], ..., a[d])

如果涉及到IT技术，那么你需要寻找的组合就是：

combination = (a[1] + 0, a[1] + a[2] + 1, ..., a[1] + a[2] + ... + a[d] + d - 1)

索引可以使用维基百科页面上的公式轻松计算。

- Tom De Caluwé

Answer 2

更好的、更面向对象的解决方案是创建单项式（Monomial）和多项式（Polynomial）类。多项式类封装了一组单项式，这样就可以轻松地模拟像...这样的病态情况。

y(x) = 1.0 + x^50

只使用两个术语而不是51个的解决方案。

另一种解决方案是使用一个映射/字典，其中键是指数，值是系数。这将仅需要两个条目来解决我的特殊情况。如果您拥有C/C++哈希映射，则可以开始工作。

就个人而言，即使多项式包含1000个术语，我认为使用数组的天真方式也不会太可怕。内存很便宜；那个数组不会让你崩溃。

- duffymo

---

这对于单变量的多项式来说效果很好。但随着变量数量的增加，OP正在寻找一种存储信息的方法。 - Teepeemm

那么它就是一个哈希映射，其中键是指数，值是每个变量的系数列表。 - duffymo

我确实在使用C++，但我担心哈希映射就像用ABC武器杀一只苍蝇。此外，您的病态案例永远不会发生。RAM是一个问题，缓存未命中也是一个问题，因为将同时使用大量多项式。此外，浪费的数组条目比例随着维度的增加而非常快速地增长。 - ANSI C Mastah

指数是复杂的部分，而不是系数。天真的方法需要（n+1）^d个术语，这很容易使你的RAM不堪重负。但是，如果哈希键是d个指数的列表，则它最多具有（n+d）选择n个键，并且一切都应该相当简单（为什么不用火箭筒打苍蝇呢？）。 - Teepeemm

@Teepeemm：是的，问题在于大多数(n+1)^d系数都是无意义的。有时候用火箭筒打苍蝇确实很酷（倒入液氮也很有趣），但是随之而来的副作用会变得乏味。不过说真的，哈希映射是运行时的东西，而我希望能够生成一些可能在编译时就能生成的东西...在那种情况下，哈希映射会严重拖慢代码的速度。 - ANSI C Mastah