“24点”的算法分析
楔子
论坛上有人在问怎样写计算24点的程序。我觉得这个题目挺有趣的，于是就自己写了一个。虽然这个程序也能运行，而且还曾帮两个同事解决了他们孩子的作业问题，但是我却并不满意。原因很简单：它虽然能列举出所有可能的组合，但这只是我预先分析的结果。如果给出的数字不是4个，而是5个或6个，那么这段程序就彻底报废了。更重要的是，如果有5个，6个或者更多的数字，事先分析的办法也行不通了。因此我必须寻找一个真正的算法。
算法分析
基本的运算只有四种，加、减、乘、除。因此，不论一个算式有多复杂，我们总可以把它概括成一个基本的加减乘除算式，只是运算符的左边和（或）右边不是一个简单的数，而是一个复杂的算式罢了。于是，我们的第一个任务，就是把一个集合拆解成两个集合，并且枚举出其所有的可能性。
分拆集合
首先要声明，说集合实际上并不准确。集合里面不能有重复的元素，但是计算24点的数字却可以重复。不过由于这个算法的思路是源自于集合运算，因此我还是把它称为“集合的分拆”。
那么怎样才能将一个集合分拆开来，并且枚举出其所有的可能性呢？我们都知道，如果一个集合有n个元素，那么它总共会有2**n个子集[1]。因为根据排列组合的乘法原则，对于其任意一个子集，每个元素都有两种状态，属于或不属于。因此，n个元素就会有2**n个子集。于是：
def enumerateAllSubsets(elements) :
def appendElement(orig_subsets, element) :
result = []
for set in orig_subsets :
result.append(set)
tmp = []
for ele in set :
tmp.append(ele)
tmp.append(element)
result.append(tmp)
return result
result = [[]]
for e in elements :
result = appendElement(result, e)
for e in result :
e.sort()
return result
这段程序的思路是这样的：假设有一个集合，它的子集集合是orig_subsets，那么当这个集合增加一个元素element之后，appendElement方法就负责返回这个新集合的子集集合。而enumerateAllSubsets先创建一个只包含空集的集合。这个只含空集的集合，就是空集的子集集合。然后我们依次往空集里面添加元素，并且利用appendElement获取其子集的集合。这样等我们把elements全都加进去之后，也就获得了elements的子集集合了。
enumerateAllSubsets所返回的子集集合并不能直接用于24点的计算，因此我们必须先做一些准备工作——去除空集和全集。由于集合中可能会有重复的数字，为了减少运算量，我们还要去除重复的子集。
def getSets (elements):
elements.sort()
tmp_result = enumerateAllSubsets(elements)
tmp_result.remove([])
tmp_result.remove(elements)
result = []
for e in tmp_result :
e.sort()
try:
result.index(e)
except ValueError:
result.append(e)
return result
此外，我们还需要一个计算补集的函数。
def suppSet (fullSet, subSet):
result = []
for item in fullSet : # 由于可能会有重复的元素，因此不能写
result.append(item) # for item in fullSet:
for item in subSet : # if not item in subSet :
result.remove(item) # result.append(item)
return result
构造算式
就这个算法而言，算式的构造并不难，但是很烦。下面我们用二叉树来表示算式，用递归来求值和打印。
ADD = "+"
MIN = "-"
MUL = "*"
DIV = "/"
TYPE_OF_NUMBERS = (type(1), type(1.0))
class equationTree(object) :
def __init__ (self, left_tree, operator=None, right_tree=None):
self.left_tree = left_tree
self.right_tree = right_tree
self.operator = operator
def value (self):
if not self.operator :
return float(self.left_tree)
else:
if type(self.left_tree) in TYPE_OF_NUMBERS:
str_to_calc = str(float(self.left_tree))
else:
str_to_calc = str(self.left_tree.value())
str_to_calc += self.operator
if type(self.right_tree) in TYPE_OF_NUMBERS:
str_to_calc += str(float(self.right_tree))
else:
str_to_calc += str(self.right_tree.value())
try:
## 1. 出现 ZeroDivError的时候，这个算式的值就为None
## 2. 这要这个算式的某一部分的值为None，那么这个算式的值就是None
result = eval(str_to_calc)
except :
result = None
return result
def __repr__ (self):
if type(self.left_tree) in TYPE_OF_NUMBERS :
left_repr = str(self.left_tree)
else:
left_repr = `self.left_tree`
if type(self.right_tree) in TYPE_OF_NUMBERS :
right_repr = str(self.right_tree)
else:
right_repr = `self.right_tree`
if not self.operator :
return left_repr
else:
if self.operator == ADD:
pass
elif self.operator == MIN:
if type(self.right_tree) not in TYPE_OF_NUMBERS and self.right_tree.operator in (ADD, MIN):
right_repr = "(" + right_repr + ")"
elif self.operator == MUL:
if type(self.left_tree) not in TYPE_OF_NUMBERS and self.left_tree.operator in (ADD, MIN) :
left_repr = "(" + left_repr + ')'
if type(self.right_tree) not in TYPE_OF_NUMBERS and self.right_tree.operator in (ADD, MIN):
right_repr = "(" + right_repr +')'
else:
if type(self.right_tree) not in TYPE_OF_NUMBERS and self.right_tree.operator :
right_repr = "(" + right_repr + ')'
if type(self.left_tree) not in TYPE_OF_NUMBERS and (self.left_tree.operator in (ADD, MIN)):
left_repr = "(" + left_repr + ')'
return left_repr + self.operator + right_repr
枚举算式
接下来我们就用上面准备的这两个工具来枚举出所有的算式。还是用递归。
def getEqTrees (elements):
if len(elements) == 1 :
return [equationTree(elements[0])]
elif len(elements) == 2:
return [equationTree(elements[0], ADD, elements[1]),
equationTree(elements[0], MIN, elements[1]),
equationTree(elements[0], MUL, elements[1]),
equationTree(elements[0], DIV, elements[1]),
equationTree(elements[1], MIN, elements[0]),
equationTree(elements[1], DIV, elements[0]),]
else:
result = []
for e in getSets(elements):
for left_tree in getEqTrees(e) :
for right_tree in getEqTrees(suppSet(elements, e)) :
for op in (ADD, MIN, MUL, DIV) :
result.append(equationTree(left_tree, op, right_tree))
return result
结尾
程序已经大致完成了，最有只要加一段主程序就能运行了[2]。
if __name__ == '__main__' :
print """
Written by shhgs, on March 3, 2004."""
result = []
print """
Please input a tuple of integer, delimited by colon.
For example: 1, 2, 3, 4
Don't try to input more than 5 numbers,
otherwise it will take a long long time to respond.
Four is recommended.
"""
tup = input('Please input the tuple of integers: ')
for eq in getEqTrees(list(tup)):
if eq.value() == 24 :
result.append(eq)
print "%s = 24" % eq
我用4个变量和5个变量测试过这段程序，都获得了成功。但是6变量算了一个小时还是没结果，最后我放弃了。我想大概还是计算量太大了。有兴趣的读者可以试试。顺便说一下，我的测试平台是P4 Celeron 2.0G, 1G内存，Windows 2000 SP4。如果你的配置低于这个，建议就不要试了。
[1]这个算法是用Python实现的，因此这里用Python的表示方法。有兴趣的读者可以试着用Java或其他语言来实现。
[2]这个程序里面有中文注释，所以运行的时候会出现警告。要想解决这个问题，可以在程序的第一行加上：
# -*- coding: mbcs -*-
