10897 如何不重複地枚舉 24 點算式？（中）
本系列的上篇介紹了枚舉由 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 收錄：
A006351 - OEIS推薦閱讀：