[Python知识库]Point 24点计算Python编程思路(一)

24点计算编程思路(Python Programming for Point 24 Game)

一、穷举法解决24点计算问题

目的：把四个数字的所有代数运算式进行尝试计算，要设法把所有排列计算一遍。

(1) 四个整数位置的排列，用 $0,1,2,3$ 表示位置，排列是不能重复的，
所以有 $A_4^4$ 种情况，即 $4！=4\times 3\times 2\times 1=24$ 种；

from itertools import permutations

def perms(narr):
    '''得到给定数组的全排列narray=[a,b,c,d]，4个数有4！个不同的排列
    建议用集合，可以预先删除重复项。
    '''
    return set(permutations(narr))

(2) 三个运算符的变化，每个运算符为 + - * /, 可以相同，所以，
由乘法原理可得有 $4\times 4\times 4=4^3=64$ 种;

def operations(ndim):
    '''穷举各种运算排列，含重复运算，ndim = 给定数个数-1
    4个数，需要3个运算符号才能连起来。
    '''
    basic_ops = ['+','-','*','/']
    return product(basic_ops, repeat = ndim)

(3) 三个运算符的优先级，就是括号位置的变化，可能性为 $A_3^3?1=3!?1=6?1=5$ 种，说明如下。

要考虑运算顺序，譬如：设四张牌为 $a、b、c、d$，代表4个数，运算符为 $①、②、③$，代表3个数学运算符号。
代数表达式为 $a①b②c③d$。
这 3 个运算符的运算顺序有 $3!=6$ 种，分别是：
$1.①②③2.①③②3.②①③$
$4.②③①5.③①②6.③②①$
等价的表达式分别是：
$1.[(a①b)②c]③d2.(a①b)②(c③d)3.[a①(b②c)]③d$
$4.a①[(b②c)③d]5.(a①b)②(c③d)6.a①[b②(c③d)]$
(2.)与(5.)等价

def get_expr(a, ops):
    #TODO: 清除 a+b=b+a, a*b=b*a的情形, 满足交换律只取一种，满足结合律也只取一种。
    if len(a) == 4:
        exp1 = '(({0}{1}{2}){3}{4}){5}{6}'.format(a[0], ops[0], a[1], ops[1], a[2], ops[2], a[3])
        exp2 = '({0}{1}{2}){3}({4}{5}{6})'.format(a[0], ops[0], a[1], ops[1], a[2], ops[2], a[3])
        exp3 = '({0}{1}({2}{3}{4})){5}{6}'.format(a[0], ops[0], a[1], ops[1], a[2], ops[2], a[3])
        exp4 = '{0}{1}(({2}{3}{4}){5}{6})'.format(a[0], ops[0], a[1], ops[1], a[2], ops[2], a[3])
        exp5 = '{0}{1}({2}{3}({4}{5}{6}))'.format(a[0], ops[0], a[1], ops[1], a[2], ops[2], a[3])
        expr = [exp1, exp2, exp3, exp4, exp5]
    if len(a) == 3:
        exp1 = '({0}{1}{2}){3}{4}'.format(a[0], ops[0], a[1], ops[1], a[2])
        exp2 = '{0}{1}({2}{3}{4})'.format(a[0], ops[0], a[1], ops[1], a[2])
        expr = [exp1, exp2]

    return expr

综上所述，所有可能的代数表达式为：$24\times 64\times 5=7680$ 种。

（4）对这组排列逐一进行运算，看是否是 $24$，就可以得到最终所有式子。
在运算过程中除法的特殊性：除数不能为零。采用 try...except 跳过除数为零的情形。
因为可能会用到除法，所以要考虑浮点数的精度问题，采用 math 库提供的内部函数 isclose() 达到比较目的。

def find24(narr):
    '''找到所有结果是24的运算式,
    TODO: 如何清理重复的算式，可以交换的算式, 譬如 a*b = b*a, a+b = b+a
    '''

    ops = set(operations(len(narr)-1))  #
    perms_arr = perms(narr)  #清除了带重复数的排列
    reslist = set()  #集合对元素唯一性有要求

    for arr1 in perms_arr:
        for op in ops:
            expressions = get_expr(arr1, op)  # 组合数组和运算符号组
            #print(expr)
            for expr in expressions:
                try:
                    res = eval(expr)  # 计算表达式的值用eval(source)
                except ZeroDivisionError:
                    continue

                if isclose(res, RESULTN):
                    reslist.add('{0}={1}'.format(expr, int(res)))  #int(24.0)=24

    return reslist  # 集合可以清除相同项