inj*_*joy 5 algorithm math cartesian-product
例如,我们有一组公式如下:
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.
我想问一下,有一种算法来确定一组公式中笛卡尔积的最小数量吗？还拿出这些产品？
首先，我将编写一组公式作为由 分隔的项+，因为您正在寻找的转换在代数上是有意义的（除了您不想将数字组合成2+3）5。
您可用的基本操作是因式分解：将两个项组合ABC+ABD成AB(C+D)。根据您的评论，您只能生成由单因子项之和组成的新因子，如C+D前面的示例所示；你不被允许将eg 分解ABCD+ABDE为AB(CD+DE)。
当且仅当它们完全共享 k-1 个因子时，您可以对 2 个 k 因子项进行因式分解。 （例如，在我的ABC+ABD示例中 k=3。）每次这样的因式分解都会将集合中的项数减少 1：删除 2 项并重新添加 1 项。
当组合 3 个或更多项时，多次执行此操作是有效的：ABC+ABD+ABE可以首先因式分解为AB(C+D)+ABE，然后将这 2 项再次因式分解为AB(C+D+E)。请注意，我们在总和中列出项或乘积中的因子的顺序并不重要，并且在构建包含 3 个或更多项的因子时我们执行因式分解步骤的顺序也不重要。
然后，我们可以将问题框架为图中的搜索问题，其中起始顶点对应于原始公式（B*2*j + B*3*i + ... + D*3*j在您的示例中），并且从每个顶点 v 都有弧线到其子顶点，每个顶点对应于执行的结果v 上的某些因式分解将为可以对其执行的每个可能的因式分解拥有一个子顶点；如果 v 中有 m 个项，那么这意味着在最坏的情况下它最多可能有 m(m-1)/2 个子项，因为所有 m 个项可能共享 k-1 个因子的完整补集，这意味着它们中的任何一对都可以组合。
如果一个顶点没有可以通过因式分解组合的项对，那么它就是一个“叶子”——它没有子节点，并且无法进一步处理。我们想要找到的是项数最少的叶顶点。由于对应于图中的弧的每个因式分解都会将项数减少 1，因此这相当于搜索最深的可能顶点。这可以使用 DFS 或 BFS 来完成。seen但请注意，使用此方法可以多次生成相同的表达式（顶点），因此维护一个记录已处理的所有表达式的哈希表对于性能至关重要；然后，如果我们访问一个顶点，尝试为其生成一个子节点，并看到该子节点已经在 中seen，我们就避免再次访问该子节点。
为了减轻通过同一组分解的多个不同顺序生成相同表达式的现象，您可以添加一条规则：以某种方式对 v 的子分解进行排序，这样如果有 n 个子分解，它们对应于分解 1, 2,...。 .., n 在此排序中，并在每个子顶点中的单独“已跳过”字段中记录为生成该子顶点而跳过的早期（按排序）因式分解的集合。然后，在访问顶点时，避免生成任何“已跳过”的因式分解作为子项，因为这样做会创建一个与其他现有顶点相同的顶点（通过以相反的顺序执行同一对操作）。
可能还有其他可用的加速方法可以减少首先生成的重复顶点的数量，但这应该足以获得小问题的结果。