Point 24点计算Python编程思路(一)

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

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

from itertools import permutations

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

(2) 三个运算符的变化，每个运算符为 + - * /, 可以相同，所以，
由乘法原理可得有 4 × 4 × 4 = 4 3 = 64 4times 4times 4 = 4^3 = 64 4×4×4=43=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_3^3-1=3!-1 = 6-1 = 5 A33​−1=3!−1=6−1=5 种，说明如下。

要考虑运算顺序，譬如：设四张牌为 a 、 b 、 c 、 d a、b、c、d a、b、c、d，代表4个数，运算符为 ① 、 ② 、 ③ ①、②、③ ①、②、③，代表3个数学运算符号。
代数表达式为 a ① b ② c ③ d a ① b ② c ③ d a①b②c③d。
这 3 个运算符的运算顺序有 3 ! = 6 3!=6 3!=6 种，分别是：
1.    ① ② ③ 2.    ① ③ ② 3.    ② ① ③ 1.;①②③ quad 2.;①③② quad 3.;②①③ 1.①②③2.①③②3.②①③
4.    ② ③ ① 5.    ③ ① ② 6.    ③ ② ① 4.;②③① quad 5.;③①② quad 6.;③②① 4.②③①5.③①②6.③②①
等价的表达式分别是：
1.    [ ( a ① b ) ② c ] ③ d 2.    ( a ① b ) ② ( c ③ d ) 3.    [ a ① ( b ② c ) ] ③ d 1.; [(a①b)②c]③dquad 2.; (a①b)②(c③d)quad 3.; [a①(b②c)]③d 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 ) ] 4.; a①[(b②c)③d]quad 5.; (a①b)②(c③d)quad 6.; 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 × 64 × 5 = 7680 24times 64times 5=7680 24×64×5=7680 种。

（4）对这组排列逐一进行运算，看是否是 24 24 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  # 集合可以清除相同项