首先,我会将一组公式写成由
+
分隔的项的形式,因为您要寻找的转换在代数上是有意义的(除了您不想将像
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,并在每个子节点中单独记录“已跳过”的字段,以记录生成此子节点而跳过的早期(在排序中)的因式分解集。然后,在访问一个顶点时,避免产生任何它的“已跳过”的因式分解作为子节点,因为这样做会创建一个与某个其他现有顶点完全相同的顶点(通过以相反的顺序执行相同的操作)。
可能还有其他可用的加速方法,可以减少首先生成的重复顶点的数量,但对于小问题,这应该足够得到结果。
B*2*j + B*3*i + ... + D*3*j
。 - j_random_hacker