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

03-03

　　「24 點」是一個歷史悠久的遊戲：任取 4 張撲克牌，如何用「加、減、乘、除」運算算出 24？除了作為消遣，它還是一道經典的編程入門題，其基本思路是：枚舉所有可能的算式，逐個檢驗結果是否等於 24。

　　在這一系列專欄中，我們忽略「24」，而把目光聚焦在「枚舉算式」上。換句話說，我們來枚舉由 4 個變數 a, b, c, d（也可以推廣至 n 個變數）經過四則運算可以組成的所有算式，而不代入具體數值。我們的程序要輸出的，就是 a + b - c * d、a / (b * (c + d)) 這樣所有的算式。

　　枚舉算式的思路有很多，比如：

不分層枚舉：分別枚舉 n 個變數的順序、n-1 個運算符是什麼，以及加括弧的方式。「加括弧的方式」不太直接，但可以用「n-1 個運算符的計算順序」來代替。這種思路適合用來計算算式的總數： $n! cdot 4^{n-1} cdot (n-1)!$ ，但如果真要枚舉算式，程序寫起來並不方便。
自頂向下枚舉：枚舉最頂層的運算符，並把所有變數分成兩組放在運算符的兩邊，然後遞歸地枚舉兩邊的算式。這種做法需要枚舉「所有變數的集合」的所有子集，寫程序也不方便。
自底向上枚舉：把每個變數都看作算式，每次任取兩個算式和一個運算符，組成新算式後放回算式集合，並遞歸下去，直到集合中只剩一個算式為止。這種思路，在遞歸的每一層上要做的事情是最簡單的，所以本文將採用這種思路。

一、算式的表示方式

　　在枚舉算式之前，我們首先要設計算式的表示方式。最簡單的辦法是使用字元串。但在下文中可以看到，為了判斷在哪裡需要加括弧，以及避免重複，我們需要從算式中提取一些信息，而從字元串中提取這些信息就很不方便了。於是我們選用樹形結構來表示算式。一個算式表示為一棵樹，樹的內部結點為運算符，葉子結點為變數。例如，a / (b * (c + d)) 這個算式就用如下的樹來表示：

　　樹的結點可以用一個類來實現，目前它只需要三個屬性：一個字元（運算符或者表示變數的字母），一個左孩子指針，一個右孩子指針。用 Python 語言實現如下：

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

　　既然開始設計算式的表示方式了，我們就順便考慮一下怎麼輸出一個算式，即怎麼把一棵樹轉換成一個字元串。這也是一個遞歸的過程：

如果根結點的字元是個字母，那麼這棵樹僅代表一個變數，只需輸出相應的字母；
否則，這棵樹代表一個算式，可以將兩棵子樹分別轉換成字元串後，用根結點的運算符連接起來。

　　這裡有一個比較麻煩的問題，就是兩棵子樹轉換成的字元串，可能需要加括弧。我們當然可以不分青紅皂白地一律加括弧，但這樣輸出的算式讀起來就比較困難。最省括弧的方法如下：

如果子樹只代表一個變數，那麼不加括弧；
左子樹需要加括弧的情況為：根的運算符的優先順序高於左子樹，即根的運算符為乘除，左子樹的運算符為加減；
右子樹需要加括弧的情況有三種：

根的運算符的優先順序高於右子樹，即根的運算符為乘除，右子樹的運算符為加減；
根的運算符為減，右子樹的運算符為加減；
根的運算符為除，右子樹的運算符為乘除。

右子樹需要加括弧的三種情況，可以合併為：根的運算符為除，或者根的運算符為乘減，且右子樹的運算符為加減。

由此可以實現 Node 類的 __str__ 方法，這樣就可以通過 str(root) 把一棵樹表示的算式輸出出來了。

def __str__(self): if self.ch not in +-*/: return self.ch # 單變數不加括弧 left = str(self.left) # 左子樹轉字元串 right = str(self.right) # 右子樹轉字元串 if self.ch in */ and self.left.ch in +-: left = ( + left + ) # 左子樹加括弧 if self.ch == / and self.right.ch in +-*/ or self.ch in *- and self.right.ch in +-: right = ( + right + ) # 右子樹加括弧 return left + + self.ch + + right # 用根結點的運算符相連

二、樸素的枚舉演算法

　　下面我們實現開頭所說的「自底向上」的枚舉演算法，即每次取兩個算式和一個運算符，並把運算結果放回集合。

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]): # 枚舉運算符 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

　　我在輸出結果時使用了 yield 而不是 print 語句，這樣 DFS 函數將成為一個 generator，方便主程序捕捉到所有算式，並進行「統計個數」等後續工作。actions 函數接收兩棵子樹，枚舉根結點的運算符，並返回它們組成的整棵樹。由於在 DFS 函數中我們限定了 i < j，所以 actions 函數也要枚舉輸入的兩棵子樹誰在左，誰在右。

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

我之所以把 actions 單獨寫成一個函數，是因為後續文章中，大部分的改進都體現在這個函數上。

　　有了上面這些函數後，就可以通過如下的主程序來輸出所有由 4 個變數組成的算式了：

n = 4 # 變數個數trees = [Node(chr(97 + i)) for i in range(n)] # 初始時有 n 個由單變數組成的算式expressions = list(DFS(trees))for ex in expressions: print ex

用 len(expressions) 可以獲得算式的總數，結果是 9216。不難驗證， $n! cdot 4^{n-1} cdot (n-1)!$ 在 n = 4 時確實等於 9216。

三、算式重複的統計

　　用上文的方法枚舉出的 9216 個算式中，會有很多重複，例如算式 a + b + c + d 就會出現 6 次。除了嚴格的重複以外，還會有很多等價的算式，比如 b + d + c + a 就跟 a + b + c + d 是等價的。我們來統計一下這些算式中，不重複、不等價的算式各有多少個。

　　「不重複」很好統計。主程序執行完畢後，expressions 列表保存了所有的算式，那麼len(set(expressions))就可以給出不重複的算式的個數了。

　　「不等價」則困難一些，但我們可以投機取巧。給所有的變數都取一個比較大的隨機數代進去，這樣不等價的算式就幾乎一定算出不等價的結果。為了保持精度，我們用 Python 提供的分數類（fractions）表示中間結果。統計不等價的算式個數的代碼如下：

from fractions import Fractiona = Fraction(31415); b = Fraction(92653); c = Fraction(58979); d = Fraction(32384)print len(set(eval(ex) for ex in expressions))

　　由此可以統計出，在 9216 個算式中，不重複的算式有 5856 個，不等價的算式僅有 1170 個。

四、算式重複的原因

　　在「24 點」這個應用中，對重複或等價的算式逐個檢查是否等於 24，是純粹浪費時間。所以在枚舉算式時，我們希望在重複或等價的算式中，僅枚舉一個代表。為此，我們需要弄清重複和等價算式產生的原因。在下文中，我們提到重複時，也包括等價。

　　產生重複算式的最明顯的原因，就是加法和乘法具有交換律和結合律。a + b 等價於 b + a，而下面兩棵樹都會輸出 a + b + c。

　　當加減法混合，或者乘除法混合的時候，有時也會有結合律，例如 (a + b) - c 等價於 a + (b - c)。除此之外，減法和除法還可以通過「去括弧」形成等價的算式，例如 a - (b + c) 等價於 a - b - c，a / (b / c) 等價於 a / b * c。

　　減法還有一個特別煩人的性質，即交換被減數與減數（下簡稱反轉減號）時，結果只差一個負號。若在一個算式中反轉某一個減號，而算式中另外一個地方有一個加或減號可以配合它變成減或加號，那麼就可以得到等價算式。例如，a + (b / (c - d)) 等價於 a - (b / (d - c))，這裡最上層的加號變成了減號，以配合 c、d 的交換。另外，若一個單項式中含有多個減號，就也可以同時反轉兩個減號，得到等價算式，例如 (a - b) * (c - d) 等價於 (b - a) * (d - c)。之所以說這個性質特別煩人，是因為它的作用不是局部的，而是可以影響到樹中相距甚遠的兩個部分。

　　上面列舉的原因，全都與四則運算的性質有關。但是，算式的重複，還有一個與四則運算性質無關，而僅與運算順序有關的原因。我們看算式 (a + b) * (c - d)：這裡面的加法和減法互不依賴，或者可以稱為「獨立」的。在遞歸過程中，有可能第一層計算加法、第二層計算減法，也有可能第一層計算減法、第二層計算加法，但這兩條路徑到了第三層時都會面臨同樣的算式集合 [a+b, c-d]，之後不管進行什麼運算，都會得到重複的算式。這種產生重複的原因，可以概括為「獨立運算的順序不唯一」。

　　本系列專欄的後面兩篇文章，就來研究如何避免這五種重複。本篇為上篇；中篇暫時忽略減法與除法，介紹如何避免由交換律、結合律、獨立運算順序不唯一造成的重複；下篇重新引入減法與除法，介紹如何進一步避免由去括弧、反轉減號造成的重複。