从一组公式中提取最少笛卡尔积的算法是什么？

Question

例如，我们有以下一组公式：

B*2*j
B*3*i
B*3*j
C*2*j
C*3*i
C*3*j
D*2*i
D*2*j
D*3*i
D*3*j

我们可以使用三个笛卡尔积来表示上述公式:

D*(2+3)*(i+j)
(B+c)*3*(i+j)
(B+C)*2*j

所以总数是3。我们也可以有以下内容：

3*(B+C+D)*(i+j)
2*(B+C)*D
2*D*(i+j)

这也是3。

我想问一下，是否有算法可以确定从一组公式中确定笛卡尔积的最小数量？还能够列出这些积吗？

- injoy

---

你可能想要在http://math.stackexchange.com上发布。 - barak manos

谢谢。我不知道那个。 - injoy

我希望我的问题出现在两个网站上。因为这个问题可能与计算机科学中的相关算法有关。 - injoy

我猜“总因子”中只能出现单个因子，对吗？否则，您可以简单地形成一个将所有项相加的单个公式：B*2*j + B*3*i + ... + D*3*j。 - j_random_hacker

顺便提一下，在你对示例问题的第二个答案中，第二项需要添加“*j”。 - j_random_hacker

Answer 1

首先，我会将一组公式写成由+分隔的项的形式，因为您要寻找的转换在代数上是有意义的（除了您不想将像2+3这样的数字组合成5之外）。

您可以使用的基本操作是因式分解：将两个项（如ABC+ABD）组合成一个项（AB(C+D)）。根据您的评论，您只能生成由单因素项的总和组成的新因子，例如前面示例中的C+D；您不能将ABCD+ABDE这样的表达式因式分解为AB(CD+DE)。 如果两个k个因子的项恰好共享k-1个因子，则可以对其进行因式分解。 （例如，在我的ABC+ABD示例中，k=3。）每次这样的分解都会将集合中的项数减少1：删除2个项并添加1个项。

当组合三个或更多项时，多次执行此操作可行：ABC+ABD+ABE可以首先因式分解为AB(C+D)+ABE，然后这两个项再次因式分解为AB(C+D+E)。请注意，在求和中列出项或在乘积中列出因子的顺序无关紧要，而且在构建包含3个或更多项的因子时执行因式分解步骤的顺序也无关紧要。

然后，我们可以将问题作为图形搜索问题来表述，在该问题中，起始顶点对应于原始公式（在您的示例中为B*2*j + B*3*i + ... + D*3*j），并且从每个顶点v到其子顶点发出弧，这些子顶点各自对应于对v执行某些因式分解的结果。对于v，它将有一个子顶点，对应于可以在其上执行的每个可能的因式分解；如果v中有m个项，则这意味着在最坏的情况下，它可能最多有m(m-1)/2个子顶点，因为所有m个项都可能共享k-1个因子的完整补集，这意味着它们中的任何一对都可以组合。

如果一个顶点没有可以通过因式分解组合的项对，则它是一个“叶子”——它没有孩子，并且不能再进一步处理。我们要找到的是具有最少项数的叶子顶点。由于每个因式分解都对应于图中的一条弧，将项数减少了1，这等价于搜索具有最深度可能的顶点。这可以使用DFS或BFS完成。但请注意，使用此方法可以生成许多相同的表达式（顶点），因此为了性能至关重要，需要维护一个记录已处理过的所有表达式的hashtable seen，然后如果我们访问一个顶点，尝试为其生成一个子节点，并看到该子节点已经在seen中，我们就避免第二次访问该子节点。

为了缓解通过同一组因式分解的多个不同排序生成相同表达式的现象，您可以添加一个规则：按某种方式排序 v 的子节点因式分解，使得如果有n个子节点，则它们对应于此排序中的因式分解1、2、...、n，并在每个子节点中单独记录“已跳过”的字段，以记录生成此子节点而跳过的早期（在排序中）的因式分解集。然后，在访问一个顶点时，避免产生任何它的“已跳过”的因式分解作为子节点，因为这样做会创建一个与某个其他现有顶点完全相同的顶点（通过以相反的顺序执行相同的操作）。

可能还有其他可用的加速方法，可以减少首先生成的重复顶点的数量，但对于小问题，这应该足够得到结果。

- j_random_hacker

---

如果有n个可能的（部分）因式分解，那么如果没有“已经跳过”的想法，它应该会访问每一个因式分解一次，但它也会花费时间生成每个节点多达O(m^2)个子节点，其中所有子节点都可能由于之前已经被看到而被丢弃。n可以是m个叶子上标记树的数量。有了“已经跳过”，应该可以避免生成一些或所有被seen丢弃的子节点，尽管我不知道有多少。 - j_random_hacker

嗨，@j_random_hacker，倒数第二段是在谈论“seen”哈希表的实现吗？还是完全不同的事情？ - injoy

谢谢你的帮助！我刚刚无法理解这种方式。你能给我一个例子吗？ - injoy

顺便说一下，我使用C ++实现了这个算法。当因数数量较少时，它可以很好地工作。但是当因数达到13个时，执行时间变得非常长，以至于我不得不终止程序。 - injoy

答案是“否”，所以我们继续创建这个子级（同时记录到目前为止在构建中使用的最高对是 ABD+ABE）。另一方面，当我们创建根节点的第二个子级 AB(C+E)+ABD 时，我们记录其最高对为 ABC+ABE。当我们尝试创建它的子级 AB(C+D+E) 时，我们看到这意味着额外的对 ABC+ABD 和 ABD+ABE；但第一个对低于 ABC+ABE，因此我们放弃该子级。根节点的第三个子级同样如此。然而，我并不确定这是否比仅使用哈希表更快。 - j_random_hacker

Answer 2

将您的总和以矩阵形式写下。然后您所要求的是该矩阵的秩，并对其进行相应的二元乘积分解。这种分解远非唯一。

            [ 3  5 ]   [ i ] 
[ B C D ] * | 3  5 | * [ j ]
            [ 5  5 ]   

正如大家所看到的，在中间的矩阵具有完全秩2

---

如果您打算将2和3也用作变量，则要求将一个三阶张量分解为最少数量的因子化项，即张量积向量。

- Lutz Lehmann