10897 如何不重複地枚舉 24 點算式？（下）

03-03

　　本系列的中篇暫時忽略了減法和除法，介紹了如何避免交換律、結合律、獨立運算順序不唯一造成的重複。本文將重新引入減法和除法，研究如何避免「去括弧」和「反轉減號」造成的重複。其中，「反轉減號」的處理尤為困難。

　　首先，我們把減法和除法重新加入 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) for op in -/: yield Node(op, left, right) yield Node(op, right, left)

一、避免「去括弧」造成的重複

　　當若干個加、減法運算混合時，減法的去括弧可以產生 a - (b + c - d) 與 a - b - c + d 這種等價算式，我們要從中選一個做代表。一個很誘人的想法是選擇 a - b - c + d 這個無括弧的算式為代表。可惜的是，無括弧算式對應的樹是向左分叉的，而我們針對交換律的改進已經排除了根結點為加法且向左分叉的樹了。好在我們還可以選擇形如 (a + d) - (b + c) 的算式做代表，即只允許最上層運算為減法，它的兩棵子樹必須都若干項相加而成。換句話說，就是在樹中，加號和減號的孩子都不能是減號。

　　上面的分析同樣適用於乘法和除法。我們選擇形如 (a * d) / (b * c) 的算式，作為乘、除法混合運算的代表。體現在樹中，就是乘號和除號的孩子都不能是除號。

　　加入了以上限制條件的 actions 函數如下所示。由於條件開始變得複雜了，我們就把加、減、乘、除四種運算分開來寫。

def actions(left, right): # 加法：兩個孩子都不能是減號；左孩子還不能是加號； # 若右孩子是加號，則左孩子和右孩子的左孩子要滿足單調性 if left.ch not in +- and right.ch != - and (right.ch != + or left.id < right.left.id): yield Node(+, left, right) # 減法：兩個孩子都不能是減號 if left.ch != - and right.ch != -: yield Node(-, left, right) yield Node(-, right, left) # 乘法：兩個孩子都不能是除號；左孩子還不能是乘號； # 若右孩子是乘號，則左孩子和右孩子的左孩子要滿足單調性 if left.ch not in */ and right.ch != / and (right.ch != * or left.id < right.left.id): yield Node(*, left, right) # 除法：兩個孩子都不能是除號 if left.ch != / and right.ch != /: yield Node(/, left, right) yield Node(/, right, left)

二、避免「反轉減號」造成的重複

　　為了避免「反轉減號」造成的重複，我們定義一個概念，叫算式的「極性」。a - b 和 b - a 這兩個算式只差一個負號，我們就稱它們是有極性的，並從中任選一者稱為正極性，另一者稱為負極性。而像 a + b、a * b 這種算式，找不到與它們只差一個負號的算式，那麼就稱為無極性。更一般的極性定義為：

　　如果一個算式可以通過反轉其中某個（或某些）減號而變成自己的相反數，那麼就稱一個算式是有極性的；這個算式和它的相反數中，任選一者稱為正極性，另一者稱為負極性。

　　這個極性有什麼用呢？舉個例子：我們定義 a - b 為正極性，b - a 為負極性；c - d 為正極性，d - c 為負極性。把 a - b 與 c - d 這兩個正極性的算式相乘，可以得到 (a - b) * (c - d)；把 b - a 與 d - c 這兩個負極性的算式相乘，可以得到等價算式 (b - a) * (d - c)。極性可以幫助我們識別出這樣的等價算式，並在其中選擇一者為代表，而捨棄另一者。

　　我們往 Node 類的定義中再添加一個屬性 polar，用來表示算式的極性。正、負、無極性分別用 +1、-1、0 表示。

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

　　顯然，初始時由單個變數組成的算式，都沒有極性。我們下面要解決的問題，就是如何計算兩個算式經過一步運算之後結果的極性，以及如何利用極性識別出等價算式。

　　這裡，乘、除法是相對簡單的。我們分三種情況討論：

如果相乘或相除的兩個算式都沒有極性，那麼結果也沒有極性。
如果相乘或相除的兩個算式中有一者有極性，那麼可以定義結果的極性與有極性的一者極性相同。舉個例子：假設一個算式 X 有正極性（即通過反轉其中某些減號變成 -X），另一個算式 Y 無極性。那麼 X * Y、X / Y、Y / X 這三個算式就會有與之成對的 (-X) * Y、(-X) / Y、Y / (-X)，故可以把前三者定義為正極性，後三者定義為負極性。這裡面沒有等價算式。
如果相乘或相除的兩個算式都有極性，情況就比較複雜了。考慮兩個有極性的算式 X 和 Y。以乘法為例，X、Y 和它們的相反數可以乘出四種結果：X * Y、X * (-Y)、(-X) * Y、(-X) * (-Y)。這四個式子兩兩等價，而兩組等價的式子互為相反數。我們不妨選擇 X * Y 和 X * (-Y) 為代表，並定義 X * Y 為正極性，X * (-Y) 為負極性；另外兩個算式則作為這兩個算式的等價算式而被捨棄。總結一下是這樣：若左子樹的極性為正，則結果被選為代表，且極性與右子樹相同；若左子樹的極性為負，則結果被捨棄。這種處理方法同樣適用於除法。

　　下面看加、減法，它們必須放到一起來看。同樣分三種情況：

如果相加的兩個算式 X、Y 都沒有極性，那麼結果 X + Y 也沒有極性；如果相減的兩個算式 X、Y 都沒有極性，那麼就在 X - Y 和 Y - X 中任取一者定義為正極性，另一者定義為負極性。
如果 X 有極性，Y 無極性，那麼 X、-X 與 Y 相加減可以得到如下 6 個算式：

[1] X + Y, [2] (-X) + Y, [3] X - Y, [4] (-X) - Y, [5] Y - X, [6] Y - (-X)
其中 [1]、[4] 互為相反數，[2]、[3] 互為相反數；[2]、[5] 等價，[1]、[6] 等價。我們捨棄 [5]、[6]，並定義 [1]、[2] 為正極性，[3]、[4] 為負極性。總結一下是這樣：有極性與無極性相加，結果為正極性；有極性減無極性，結果為負極性；無極性減有極性，結果捨棄。
如果 X、Y 都有極性，那麼 X、-X 與 Y、-Y 相加減可以得到如下 12 個算式：
[1] X + Y, [2] (-X) + Y, [3] X + (-Y), [4] (-X) + (-Y),
[5] X - Y, [6] (-X) - Y, [7] X - (-Y), [8] (-X) - (-Y),
[9] Y - X, [10] Y - (-X), [11] (-Y) - X, [12] (-Y) - (-X)

其中 [1]、[4] 互為相反數，[2]、[3] 互為相反數；[1]、[7]、[10] 等價，[2]、[8]、[9] 等價，[3]、[5]、[12] 等價，[4]、[6]、[11] 等價。於是，[5] ~ [12] 這八個算式應當全部捨棄，並可以定義 [1]、[2] 為正極性，[3]、[4] 為負極性。總結一下是這樣：兩個有極性的算式相加，結果的極性與右子樹相同；兩個有極性的算式相減，結果捨棄。

　　我們在 actions 函數中實現上面的討論，這包括計算兩個算式運算結果的極性，以及識別、捨棄等價算式。很不幸，代碼變得十分冗長了。代碼的邏輯順序與上面的討論不盡相同，請逐條對照。

def actions(left, right): # 加法：兩個孩子都不能是減號；左孩子還不能是加號； # 若右孩子是加號，則左孩子和右孩子的左孩子要滿足單調性 if left.ch not in +- and right.ch != - and (right.ch != + or left.id < right.left.id): polar = (0 if left.polar == 0 and right.polar == 0 else # 無極性 + 無極性 = 無極性 1 if left.polar == 0 or right.polar == 0 else # 有極性 + 無極性 = 正極性 right.polar) # 有極性 + 有極性 = 右子樹極性 yield Node(+, left, right, polar) # 減法：兩個孩子都不能是減號 if left.ch != - and right.ch != -: if left.polar == 0 and right.polar == 0: # 無極性 - 無極性： yield Node(-, left, right, 1) # 正過來減是正極性 yield Node(-, right, left, -1) # 反過來減是負極性 else: if left.polar == 0: yield Node(-, right, left, -1) # 有極性 - 無極性 = 負極性 # （無極性 - 有極性 = 捨棄） # （有極性 - 有極性 = 捨棄） if right.polar == 0: yield Node(-, left, right, -1) # 同上 # 乘法：兩個孩子都不能是除號；左孩子還不能是乘號； # 若右孩子是乘號，則左孩子和右孩子的左孩子要滿足單調性 if left.ch not in */ and right.ch != / and (right.ch != * or left.id < right.left.id): if left.polar == 0 or right.polar == 0: yield Node(*, left, right, left.polar + right.polar) # 無極性 * 無極性 = 無極性 # 有極性 * 無極性 = 有極性者的極性 elif left.polar > 0: yield Node(*, left, right, right.polar) # 正極性 * 有極性 = 右子樹極性 # （負極性 * 有極性 = 捨棄） # 除法：兩個孩子都不能是除號 if left.ch != / and right.ch != /: if left.polar == 0 or right.polar == 0: yield Node(/, left, right, left.polar + right.polar) # 無極性 * 無極性 = 無極性 # 有極性 * 無極性 = 有極性者的極性 yield Node(/, right, left, left.polar + right.polar) # 同上 else: if left.polar > 0: yield Node(/, left, right, right.polar) # 正極性 / 有極性 = 右子樹極性 # （負極性 / 有極性 = 捨棄） if right.polar > 0: yield Node(/, right, left, left.polar) # 同上

　　到此，我們終於避免了所有五種原因造成的重複。可以驗證，最終版程序可以不重不漏地枚舉四則運算式！

三、總結

　　本文解決了減法和除法中由「去括弧」和「反轉減號」造成的重複，修改主要體現在 actions 函數中。為了排除由「反轉減號」造成的重複，我們定義了算式的極性。極性在運算中的傳遞規律非常複雜，造成 actions 函數冗長而不優雅，我也很無奈。

　　用最終版程序可以算出，由 n 個變數經四則運算可以組成的算式個數為：

這個數列也被 The Online Encyclopedia of Integer Sequences 收錄：

A140606 - OEISoeis.org

值得一提的是，這個數列是由一位中國網友杜朝暉（音）貢獻的；頁面上兩個參考文獻鏈接，一個（已失效）指向一個中文數學論壇，一個指向百度貼吧。

　　本系列文章雖然解決了枚舉由 n 個變數組成的四則運算式時的去重問題，但仍有許多有趣的擴展問題有待研究。它們包括：

已知 n 個具體數值，不重複地枚舉它們組成的四則運算式。這裡的難點在於，具體數值中可能含有 0 和 1，它們的運算也容易產生 0 和 1。而 0 是加法單位元，1 是乘法單位元；0 與加減法結合、1 與乘除法結合會產生大量的等價算式。此外，還需要考慮「0 不能做除數」的限制。
已知若干變數，但其中有些變數出現多次（例如 3 個 a、2 個 b），不重複地枚舉它們組成的四則運算式。變數的多次出現本身就會造成許多重複算式；另外同一個變數經減法、除法運算會得到 0 和 1，於是就也面臨「加、乘法單位元」和「0 不能做除數」的問題。
已知 n 個變數，不枚舉它們組成的四則運算式，而只是求不等價算式的個數。換句話說，求 OEIS 中數列 A140606 的通項公式。如果求不出通項公式，也可以求複雜度較低的遞推公式，或者求一個漸近的通項公式。這將是一個既有趣又有難度的組合數學問題。

　　本系列文章的完整代碼，可以在 GitHub 上獲得：

MaigoAkisame/enumerate-expressionsgithub.com

10901 更新： @終軍弱冠給出了算式計數的遞推演算法，詳見他的專欄文章：

終軍弱冠：關於四則運算表達式計數問題的討論zhuanlan.zhihu.com