24點遊戲是一款老少咸宜的益智遊戲，遊戲的玩法是給出任意四個數字，通過加減乘除四則運算，計算出24。
關注，轉發，私信“01”獲取源碼和十套PDF文檔！
網上有很多24點遊戲算法，找出解法並不難，但是難在如何合適地加括號和去除等價的重複表達式上。
1. 目標和要求
我們的目標是給定任意N個正整數（N > 1），找到能夠將這N個數通過四則運算計算得出24的全部表達式，並且只在必要的時候加上括號以及去除等價的重複表達式。
首先，我們要明確什麼是合適的括號？就是指在不影響計算結果的前提下，能不加括號儘量不加括號，比如：
(15 + 8) + 7 -6 = 24 應寫作 15 + 8 + 7 -6 = 24
其次，什麼是等價的重複表達式呢？就是完全相同的表達式，或者是在加法交換率和乘法交換率的作用下，完全等價的表達式。比如：
10 + 12 + 7 - 5 = 24 等價於 10 - 5 +7 + 12 = 24
15 * 8 / (1 + 4) = 24 等價於 15 / (4 + 1) * 8 = 24
(3 + 1) * (2 + 4) = 24 等價於 (1 + 3) * (4 + 2) = 24
2. 算法
2.1. 求全部解算法
我採用的算法是降低維度的算法，即把多維問題降低到二維來解決。
比如，給定四個數字[1, 2, 3, 4]，這是一個四維問題，我們首先要將其轉換為二維問題。具體的辦法是，先將四個數字其中的兩個數字取出，然後將這兩個數字轉化為所能組成的全部表達式。
我們首先取出[1, 2]，考慮到加法交換率和乘法交換率的前提下，共有6種可能的不等價表達式，即1+2, 1-2, 1*2, 1/2, 2-1, 2/1，則四維問題就可以轉化為多組三維問題，即['1+2', 3, 4]，['1-2', 3, 4]，['1*2', 3, 4]， ['1/2', 3, 4]， ['2-1', 3, 4]， ['2/1', 3, 4]。
然後我們窮盡每一種取出兩個數的組合，使用排列組合公式即C(4, 2)，所以將四維問題轉化為三維問題共有C(4, 2) * 6 = 36種組合。
下一步是重複這一過程，將三維問題繼續轉化為二維問題，同理，每一個三維問題都可轉化為等價的二維問題，共有C(3, 2) * 6 = 18種組合。
所以，四維問題可轉化為36 * 18 = 648種二維問題，每個二維問題又有6種組合方式，所以，全部的表達式個數為648 * 6 = 3888個。
2.2. 加括號算法
在每一次二維組合成新表達式的時候，我們根據原有的兩個表達式的各自的運算符號和兩個表達式之間的運算符號的關係來判斷是否需要添加括號。
比如，a、b兩個表達式要組成新的表達式，總共會有如下幾種情況：
- 如果是a + b，則完全不需要加括號；
- 如果是a * b或者a / b，若a、b自身的運算符號是加號或減號，則應加括號，如，a = a1 + a2，b為數字，則a * b = (a1 + a2) * b；
- 如果是a - b，若b為加號或減號，則b應加括號，如，b = b1 - b2，a = a1 + b2，則 a - b = a1 + a2 - (b1 - b2)，但值得注意的是，a1 + a2 - (b1 - b2) 其實等價於 a1 + a2 - b1 + b2，這種情況在其他的組合中其實已經存在。因此，可以無需再考慮括號問題；
- 如果是a / b，若b的符號是乘號或除號，原本理應也要加括號，但其實這種情況與上一種情況類似，我們出於計算簡便考慮，可以不再考慮括號問題。
2.3. 去除等價表達式
對於一個表達式，a + b - c + d 與如下表達式均是等價的：
- a + d + b - c
- b + a + d -c
- b - c + a + d
我們可以在任何一個表達式前再加一個加號，然後使用正則表達式對錶達式進行切割成如下狀態：['+a', '+b', '-c', '+d']。
然後對其進行排序後再組合成字符串得到：
- a + b + d - c
我們將這樣的表達式稱為標準表達式，凡是通過這樣的處理方法得到的標準表達式是相同的，我們均認為是等價表達式，只保留一個標準表達式即可。
乘法交換率也是同樣的轉換方法。
3. 代碼
算法講完了，具體的代碼實現如下：
關注，轉發，私信“01”獲取源碼和十套PDF文檔！
閱讀更多 python聚集地啊 的文章
