本系列的上篇介绍了枚举由 n 个变量组成的四则运算式的方法，并指出了算式重复的五种原因：交换律、结合律、去括号、反转减号、独立运算的顺序不唯一。其中，「反转减号」涉及减法，「去括号」涉及减法与除法，我们放到下篇讨论。这一篇文章，就来研究如何枚举仅由加法和乘法组成的算式，并避免交换律、结合律、独立运算的顺序不唯一造成的重复。

　　前几天知乎上有这样一个问题：

怎样穷举完给定N个电阻的所有串并联组合的阻值？​

如果不考虑「电桥」这种特殊的电路结构，只考虑串、并联两种结构嵌套而成的电路，那么做法就跟本文所述完全一样。这是因为串、并联两种结构可以类比成加、乘法两种运算，虽然具体的运算法则不同，但它们都满足交换律、结合律。

一、避免「交换律」造成的重复

　　交换律造成的重复是最容易避免的。回顾上篇中的 actions 函数，它接收两棵子树，并枚举根结点的运算符（在此仅保留加法与乘法），返回所有可能的组合：

def actions(left, right):
    for op in '+*':
        yield Node(op, left, right)
        yield Node(op, right, left)

　　既然加法和乘法具有交换律，那就不必考虑两棵子树谁在左、谁在右了：

def actions(left, right):
    for op in '+*':
        yield Node(op, left, right)

　　喏，就是这么简单！

二、避免「结合律」造成的重复

　　由于结合律的存在，下面这些树都是等价的：

要避免结合律造成的重复，就要在这些树中选一棵做代表，并在枚举的过程中不生成未被选为代表的那些树。适合选为代表的树，必须像第一棵或最后一棵那样，只向一侧分叉。注意，在做出上一节中针对交换律的改进之后，第一棵树其实已经不会被生成了 —— 当 a+b 和 c 要组成树的时候，只能是 c 做左子树，a+b 做右子树。于是我们选择最后一棵树，也就是只向右分叉的树，作为代表。体现在代码上，就是说左子树的运算符不能与根相同。

　　由此可以把 actions 函数改造成这样：

def actions(left, right):
    for op in '+*':
        if op != left.ch:                       # 根与左子树运算符相同时，不生成算式
            yield Node(op, left, right)

　　但这样做就够了吗？并不。下面这些树都是只向右分叉的，但仍然表达了等价的算式，其原因可以归结为「交换律」和「结合律」的共同作用：

我们需要在这些树中也选取一个代表。不妨要求相加（或相乘）的各项按字典序递增，这样就只有第一棵树被选为代表，后面两棵树就不会被生成了。（思考：要求递减行不行？）

　　但是这个「字典序」仅仅适用于单个变量。若要判断下面这棵树是否为代表，就要判断 a*b 与 c 是否构成「递增」关系：

当然可以把 a*b 转换成字符串之后再去跟 c 比较，但这样不够优雅。于是我们给结点类增设一个属性 id，并要求相加（或相乘）的各项的 id 递增。具体到代码上，就是当根结点的运算符与右子树相同时，要求左子树的 id 小于右子树的左子树的 id（这句话有点绕，请好好读一读）。actions 函数的代码如下：

def actions(left, right):
   for op in '+*':
        if op != left.ch and (op != right.ch or left.id < right.left.id):
           yield Node(op, left, right)

　　相应地，Node 类的构造函数要做如下修改，来支持 id 属性：

class Node:
    def __init__(self, ch = None, left = None, right = None, id = 0):
        self.ch = ch
        self.left = left
        self.right = right
        self.id = id

　　代表单变量的结点的 id，要在主程序中赋予，其范围为 0 至 n-1：

n = 4                                                   # 变量个数
trees = [Node(chr(97 + i), id = i) for i in range(n)]   # 初始时有 n 个由单变量组成的算式
expressions = list(DFS(trees))

而代表运算符的结点的 id，则是在递归过程中赋予的，其值为当前最大的 id 加 1：

def DFS(trees):                                         # trees 为当前算式列表
    if len(trees) == 1:
        yield str(trees[0])                             # 只剩一个算式，输出
        return
    for i in range(len(trees)):                         # 枚举一棵子树
        for j in range(i + 1, len(trees)):              # 枚举另一棵子树
            for node in actions(trees[i], trees[j]):    # 枚举运算符
                node.id = trees[-1].id + 1              # 为新结点赋予 id
                new_trees = [trees[k] for k in range(len(trees)) if k != i and k != j] + [node]
                                                        # 从集合中去掉两棵子树，并加入运算结果
                for expression in DFS(new_trees):       # 递归下去
                    yield expression

　　有了 id 属性之后，我们就知道，a * b + c + d 这个算式（下图左）是不可以作为代表的，代表应该是 c + d + a * b（下图中）。那么 c + a * b + d（下图右）呢？本节中针对结合律的改进，似乎并不能排除它呀！原来，它是由上节中针对交换律的改进排除的。针对交换律的改进保证加号（或乘号）的两棵子树在 trees 列表中顺序排列，而 trees 列表中各个算式的 id 是保持递增的，所以加号（或乘号）的两棵子树的 id 就也是递增的。

三、避免「独立运算顺序不唯一」造成的重复

　　本节要解决的问题，是下面这两棵树的重复：

　　这两棵树中的 a+b 和 c+d 互不依赖，是独立运算。最底层的 a、b、c、d 分别是 0、1、2、3 号结点。在递归过程中，可能是 a 和 b 先结合得到 4 号结点，c 和 d 后结合得到 5 号结点；也可能是 c 和 d 先结合得到 4 号结点，a 和 b 后结合得到 5 号结点。针对交换律的改进可以保证在最后一步 4 号结点是左子树、5 号结点是右子树，但它无法控制 a+b 和 c+d 谁是 4 号结点、谁是 5 号结点。

　　我们希望 a+b 和 c+d 这两个运算，其中一个必须发生在另一个之前。a+b 涉及的算式 id 为 0 和 1，c+d 涉及的算式 id 为 2 和 3；我们希望 (0,1) 发生在 (2,3) 之前。一般地，设两个运算涉及的算式 id 分别为 和 ，其中 。我们希望用一个不等式约束两个运算的发生顺序。乍一看，我们既可以要求 ，也可以要求 。但仔细一想就会发现，若要求 ，则会影响到非独立的运算。比如，c 和 d（2 号和 3 号结点）相加得到 4 号结点，之后 c+d（4 号结点）想跟 a（0 号结点）相乘。此时，。由于 ，第二步运算就会被排除，但事实上两步运算是相互依赖的，不应该排除。正确的选择是要求 ，即各步运算涉及的两个算式 id 中的较大者必须递增。

　　为了实现这一约束，就要修改 DFS 函数的实现，让外层递归把「两个算式 id 中的较大者」传递给内层递归。由于 trees 列表中各个算式的 id 是递增的，外层递归其实只需要告诉内层递归自己的 j 是多少，内层递归中的 j 只能指向外层的 j 之后的算式。我们给 DFS 函数添加一个参数 minj，表示 j 可以取的最小值。注意在递归的时候，trees 列表中外层的 i、j 所指的算式会被删除，所以内层的 minj 应该是外层的 j - 1，而不是 j + 1。另外，为了枚举 i、j 方便，我们调换了 i、j 两层循环的顺序。

def DFS(trees, minj):                                   # trees 为当前算式列表
    if len(trees) == 1:
        yield str(trees[0])                             # 只剩一个算式，输出
        return
    for j in range(minj, len(trees)):                   # 枚举一棵子树
        for i in range(j):                              # 枚举另一棵子树
            for node in actions(trees[i], trees[j]):    # 枚举运算符
                node.id = trees[-1].id + 1              # 为新结点赋予 id
                new_trees = [trees[k] for k in range(len(trees)) if k != i and k != j] + [node]
                                                        # 从集合中去掉两棵子树，并加入运算结果
                for expression in DFS(new_trees, j - 1):# 递归下去
                    yield expression

　　同时，主程序必须给第一层递归设置一个 minj，其值为 1：

n = 4                                                   # 变量个数
trees = [Node(chr(97 + i), id = i) for i in range(n)]   # 初始时有 n 个由单变量组成的算式
expressions = list(DFS(trees, 1))

四、总结

　　本文针对交换律、结合律的改进，都体现在 actions 函数中。为了避免结合律造成的重复，我们给 Node 增设了一个 id 属性。针对「独立运算顺序不唯一」，我们给 DFS 函数增加了一个参数 minj。

　　实现了本文的三种改进之后，我们的程序用 4 个变量和加法、乘法可以组成 52 种算式。使用上篇第三节的方法，可以验证这 52 个算式均不重复、不等价。当然你会担心这里有没有遗漏。在上篇的程序的基础上去掉减法和除法，可以得到 1152 个算式，其中不重复的有 528 个，不等价的有 52 个。这说明本文的改进并没有遗漏。

　　用 n 个变量和加法、乘法可能组成的不等价的算式个数如下表所示：

这个数列被 The Online Encyclopedia of Integer Sequences 收录：