Hey! Hope you are having a great day so far!
今天想和大家讨论的是一道我从这学期cs的期末考试得到灵感的题：Get 24 Poker Game。说到 Get 24 Poker Game，也就是我们通常说的凑24点，大家可能都比较熟悉。但是因为这个游戏有很多变种，我们还是来简单说一下游戏的规则。老规矩，上Wikipedia：
简单来说，这个游戏需要玩家快速用随机抽出的四张牌上的整数通过常见的加减乘除计算来凑出24点来取得胜利（一定要用全4张，不可以弃牌）。不同于我们通常玩的斗地主，钓鱼等等扑克游戏，凑24点更考验玩家的数学反应能力（less fun but somewhat interesting:)）。在这里稍稍跑一下题，因为可能会有人好奇，为什么恰恰选了24这个数字。其实答案很直白，因为这个数字最容易被凑出来：24是拥有八个除数的最小整数(1, 2, 3, 4, 6, 8, 12, and 24），使用这个数字不仅仅把游戏变得更加简单（毕竟可能没有人想花一个小时在用扑克牌凑数上），还把游戏作废（目标数字凑不出来）的几率降到最小。
好了，希望大家对这个卡牌游戏已经有一些基础的认知了，但是在正式开始编这个游戏之前，我想先从这学期cs期末考试的一道题入手：
这道题有两部分，第一部分的大意是写出一个函数，让其能够以列表的形式接收三个数字并试图用加减乘除的方法来凑出目标点数（注意，这里不包括括号操作）。第二部分相对于前一部分难度更高一点，要求写出函数，让其能够接受任意数量的数字，并可通过对其进行加减乘除（这里包括括号）的操作来凑出目标点数。另外，在做这道题的时候不需要考虑备选数字没有办法凑出目标点数的情况。
我们不难看出，第二题其实和我们想要做出的卡牌游戏的解法基本上是完全重合，甚至更加简单。只需把函数的目标数字设为24，而且限制前面列表的数字数量为4，就能够做出这个游戏的解法。但第一题给考生了一个基础的思路，也就是说第一题给第二题做了很好的铺垫，能够让人更快的找到正确的逻辑，完成解题过程。所以只要解决这两道题，我们就可以很流畅的找出凑24点的最终解法（多做一道赚一道啊！）。
话不多说，我们开始！（完整代码在文末）
通过读题，我们可以发现第一题和第二题最主要的差别在以下两点上：
- 第一题只需要考虑三个数字，两个符号的排列组合，也就是说在改变运算符号时，我们只需考虑4选1，或者4选2的情况。而第二题却需要完全不同的思路，要在不确定总数字量的情况下，在每两个数字间考虑到所有排列可能。
- 第二题需要考虑到一个，或者多个括号的算法，在这种情况下，我们不能直接计算结果，因为没有办法确定括号的个数和位置。
记住以上两点：）如果我们能在做第一小题时找到关于第二小题的启发，会事半功倍的！
第一小题我们可以从运算式子的结构入手。正常写出的话，一个有三个运算数字的式子会长这个样子：
$1+2+3$
结构一目了然，三个数字，两个运算符号。如果想生成所有排列组合的可能性的话，我们可以用嵌套for循环很容易的用代码实现如下：
1 def get_all_comb(num_list): 2 '''find all arithmatic combination using the given 3 numbers''' 3 4 for op_1 in ['+','-','*','/']: # 用第一个for loop来考虑所有第一个位置的运算符号的可能性 5 for op_2 in ['+','-','*','/']: # 用第二个for loop来考虑所有第二个位置的运算符号的可能性 6 comb = str(num_list[0])+op_1+str(num_list[1])+op_2+str(num_list[2]) # 组装运算式 7 print(comb) # 打印运算式
这段代码的输出结果为 ‘1+2+3’，‘1+2-3’，‘1+2*3’...等等十六个不重复的运算式。但是我们还要考虑到所有数字的排列组合的情况，注意在以上的例子里，所有运算的数字是没有变化的，但数字位置的变化在多数情况下会对运算结果造成影响，也就是说在我们改变运算符号的同时，我们也要考虑到所有数字的排列情况（这里指permutation）。
同样，我们也可以用以上相似的嵌套循环逻辑来用代码实现：
1 def get_num_comb(num_list): 2 '''find all combination possibilities of the given 3 numbers''' 3 4 all_comb = [] # 准备收集所有排列组合 5 for i in range(3): # 三个嵌套for循环分别对应在num_list里的序数 6 for j in range(3): 7 for k in range(3): 8 if i != j and i != k and j != k: # 确定没有重复元素 9 print([num_list[i], num_list[j], num_list[k]]) #打印最终结果
但是我们可以通过以上两段代码发现，在这里用for loop来分别实现符号和数字的排列组合虽然是可行的（同理我们也可以用类似的for loop结构来），但却无法延伸到这道题的局限外，也就是说，这个思路仅限于这道题的Part 1，如果要做第二部分的话，我们需要重新写这部分的函数（这也是这两道题的第一个主要差别：数字数量的不确定性）。
为了使第一部分的解法可以延伸到第二题，我们需要换个思路。很自然的，为了解决数字数量的不确定问题，我们不能够再使用for loop这种需要定量条件的方法，而是使用递归（recursion）。
以上我们讨论到的两个问题，运算符号以及运算数字的排列组合，可以被分别写作两个递归函数。比起普通循环，递归函数的结构更加复杂。为了减少码代码时出现不必要的概念不清的错误，我们可以针对每个递归画出树形图来作结构分析。
我们先来看运算符号的递归规律，如果我们有三个需要考虑的运算位置的话，树形图便如下图：
通过观察，我们可以看到第一层有4个分支，第二层有16个，第三层有64个。不难看出，这个递归规律的复杂度是随着递归的深度而以二次增长，所以可以用Big-Oh Notation表达成 O(4^n)，n为运算符号的个数。（关于运算复杂度和常见algorithm会有后续文章跟进，在这里不做过多解释）
根据以上基础结构，我们可以用代码来写出生成运算符号的递归函数，如下：
1 def generate_comb_op(n): 2 '''find all combination of Arithmetic operators with n possible spaces for operators''' 3 # 建立base case 4 if n==0: 5 return [] # 当n为0时不返回任何操作符号 6 elif n ==1: 7 return [['+'],['-'],['*'],['/']] # 当n为1时返回基础的四个符号，注意这里需要用到list of list 8 op_list = generate_comb_op(n-1) # 因为之后要加，所以我们这里用到递归的逻辑，来找到最基本的operator_list 9 all_op_list = [] # 新建一个list来准备更新我们加了运算符号后的sublist 10 # 最后我们还是要用循环的逻辑来给我们原来list里的元素加新的符号 11 for i in op_list: 12 for j in ['+','-','*','/']: 13 all_op_list.append(i+[j]) # 这里用了新的list，来确保每个sublist的长度是相等的 14 15 return all_op_list # 最后返回最终结果
如果再次检查运算复杂度，我们不难看出这个函数的复杂度符合我们的预测，为O(4^n)。
好了，我们再来看数字的排列方法。如果想要找到固定数量的数字的所有排列方式，我们需要用到permutation的逻辑：找到所有排列（长度为n）的第一个元素，然后根据每个元素找到剩余数字的第一个元素（剩余数字排列长度为n-1），以此类推，直到最后只剩余一个数字。我们来看一下这个递归思路的树状图（此树状图用了长度为三的list为例）：
递归的第一层有三个元素，第二层有3*2=6个元素，第三层有3*2*1=6个元素，我们可以看出这个逻辑的复杂度为 O(n!), n为需要排列组合数字的个数。
Permutation的逻辑比运算符号的排列稍稍复杂，但是我们可以用类似的递归结构来解决不同的问题，代码如下：
1 def generate_permutated_list(num_list): 2 '''find permuted lists of n given numbers''' 3 # 建立base case 4 if len(num_list) == 0: 5 return [] # 当n为0时不返回任何数字 6 if len(num_list) == 1: 7 return [num_list] # 当n为1时返回所有式子，作为之后首数字的基础 8 list_of_comb = [] # 新建列表来存更新的排列 9 for i in range(len(num_list)): 10 first_num = num_list[i] # 生成首字母 11 for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，继续递归 12 list_of_comb.append([first_num] + j) #加入新的list 13 14 return list_of_comb # 最后返回最终结果
分别生成数学操作符号以及所有数字的排列组合后，我们要把两个组合整合起来，以此生成所有的排列可能性。因为这里我们不用考虑排列组合数列的不确定性的问题（每个排列的长度，以及每组数学操作符号的长度维持不变），我们可以用循环的思维来生成所有数学表达式（所有数字和数学操作符号的组合）。但是生成所有数学表达式还不能完整的解决这个问题，因为我们不仅仅要生成所有的数学表达式，还要把表达式估值并和最终的目标数字进行比较。所以在组合最终的函数之前，我们需要先写一个估值函数来方便之后的使用。
估值函数的难点在于数学操作符号的处理，因为在数学表达式里这些运算符号都是以字符串的形式表达，例如 ‘+’，‘-’，所以无法当作正常运算符号放到代码中来操作。所以在这个情况，我们要重新赋予这些字符串它们象征的含义，代码如下：
1 def modify_op(equation, op): 2 '''this function modify the given equation by only computing the section with the given operators 3 parameters: 4 equation: a list that represents a given mathematical equation which may or may not contain the 5 given numerical operators. Ex, ['1','+','2'] represents the equation 1+2 6 op: a string that is the given numerical operators''' 7 8 # 这里我们把代表数学计算的字符串和以上定义的操作函数的名字以字典的方式联系并储存起来 9 operators = {'/':division, '*':multiply, '+':add, '-':subtract} 10 11 while op in equation: # 用while循环来确保没有遗漏任何字符 12 i = equation.index(op) # 找到表达式内的第一处需要计算的字符位置 13 if op == '/' and equation[i+1] == '0': # 考虑除法操作的被除数为0的情况 14 return [''] 15 # 把表达式需要计算的部分替换成计算结果 16 equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] # 注意这里调用了前面字典里储存的函数名 17 return equation # 返回结果 18 19 def evaluate(equation): 20 '''return the evaluated result in float for the equation''' 21 22 for op in ['/','*','+','-']: # 这里需要注意标点顺序，除在最先，因为需要考虑特殊情况，乘其次，然后才是加减 23 equation = modify_op(equation, op) # 使用helper function 24 return equation[0] # 最后返回最终计算结果
这里我们需要注意，这个估值函数能够接收表达式的形式为list，而list里的每项也必须要用字符串的形式来表达。
最后，我们只要按照之前提到的思路，整合表达式，并用以上估值函数来计算表达式的值，就可以完成这道题。在给出完整代码之前，我们再来最后复习一下这道题的解题思路：
- 找出所有加减乘除的排列组合
- 找出所有数字的排列组合
- 整合所有表达式可能
- 用估值函数计算表达式
- 对比表达式答案和目标数
- 返回符合要求的表达式
好了，那我们来看一下完整代码：
1 # Write a function that takes in a list of three numbers and a target number, and 2 # returns a string that contains an expression that uses all the numbers 3 # in the list once, and results in the target. Assume that the task is possible 4 # without using parentheses. 5 # 6 # For example, get_target_noparens([3, 1, 2], 7) can return "2*3+1" or "1+2*3" 7 # (either output would be fine). 8 9 ############################################# 数学表达式生成函数 ############################################# 10 11 def generate_comb_op(n): 12 '''find all combination of Arithmetic operators with n possible spaces for operators''' 13 # 建立base case 14 if n==0: 15 return [] # 当n为0时不返回任何操作符号 16 elif n ==1: 17 return [['+'],['-'],['*'],['/']] # 当n为1时返回基础的四个符号，注意这里需要用到list of list 18 op_list = generate_comb_op(n-1) # 因为之后要加，所以我们这里用到递归的逻辑，来找到最基本的operator_list 19 all_op_list = [] # 新建一个list来准备更新我们加了运算符号后的sublist 20 # 最后我们还是要用循环的逻辑来给我们原来list里的元素加新的符号 21 for i in op_list: 22 for j in ['+','-','*','/']: 23 all_op_list.append(i+[j]) # 这里用了新的list，来确保每个sublist的长度是相等的 24 25 return all_op_list # 最后返回最终结果 26 27 28 def generate_permutated_list(num_list): 29 '''find permuted lists of n given numbers''' 30 # 建立base case 31 if len(num_list) == 0: 32 return [] # 当n为0时不返回任何数字 33 if len(num_list) == 1: 34 return [num_list] # 当n为1时返回所有式子，作为之后首数字的基础 35 list_of_comb = [] # 新建列表来存更新的排列 36 for i in range(len(num_list)): 37 first_num = num_list[i] # 生成首字母 38 for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，继续递归 39 list_of_comb.append([first_num] + j) #加入新的list 40 41 return list_of_comb # 最后返回最终结果 42 43 44 #################################### 定义所有可能出现的数学操作，包括加减乘除 #################################### 45 46 def division(a,b): # 除法比较特殊，在之后的代码里会考虑到被除数为0的情况 47 return a/b 48 def multiply(a,b): 49 return a*b 50 def add(a,b): 51 return a+b 52 def subtract(a,b): 53 return a-b 54 55 ############################################ 数学表达式处理函数 ############################################## 56 57 def modify_op(equation, op): 58 '''this function modify the given equation by only computing the section with the given operators 59 parameters: 60 equation: a list that represents a given mathematical equation which may or may not contain the 61 given numerical operators. Ex, ['1','+','2'] represents the equation 1+2 62 op: a string that is the given numerical operators''' 63 64 # 这里我们把代表数学计算的字符串和以上定义的操作函数的名字以字典的方式联系并储存起来 65 operators = {'/':division, '*':multiply, '+':add, '-':subtract} 66 67 while op in equation: # 用while循环来确保没有遗漏任何字符 68 i = equation.index(op) # 找到表达式内的第一处需要计算的字符位置 69 if op == '/' and equation[i+1] == '0': # 考虑除法操作的被除数为0的情况 70 return [''] 71 # 把表达式需要计算的部分替换成计算结果 72 equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] # 注意这里调用了前面字典里储存的函数名 73 return equation # 返回结果 74 75 def evaluate(equation): 76 '''return the evaluated result in float for the equation''' 77 78 for op in ['/','*','+','-']: # 这里需要注意标点顺序，除在最先，因为需要考虑特殊情况，乘其次，然后才是加减 79 equation = modify_op(equation, op) # 使用helper function 80 return equation[0] # 最后返回最终计算结果 81 82 ############################################# 最终使用函数 ############################################### 83 84 def get_target_noparens(num_list, target): 85 op_list = generate_comb_op(len(num_list)-1) # 找出所有加减乘除的排列组合 86 num_comb = generate_permutated_list(num_list) # 找出所有数字的排列组合 87 # 用for嵌套循环来整合所有表达式可能 88 for each_op_list in op_list: 89 for each_num_list in num_comb: 90 equation = [] # 用list初始化表达式 91 equation_str = '' # 用string表达算式 92 for i in range(len(each_op_list)): 93 equation.extend([str(each_num_list[i]), each_op_list[i]]) 94 equation_str += str(each_num_list[i]) + each_op_list[i] 95 equation.append(str(each_num_list[-1])) 96 equation_str += str(each_num_list[-1]) 97 98 result = evaluate(equation) # 表达式估值，这里要用list的形式 99 if float(result) == float(target): 100 return equation_str # 用字符串返回算式
我们稍作测试：
- get_target_noparens([1,2,3], 6)返回 1+2+3
- get_target_noparens([1,2,3], 4.5)返回 1+3/2
- get_target_noparens([23,1,3], 68)返回 23*3-1
三个测试都成功通过，那么我们的第一题就解完了。
我们这里对第一题的解法同样能够应用到第二题的基础部分，因为篇幅原因，第二题的解题方式会放到下一篇讲解，链接如下：
https://www.cnblogs.com/Lin-z/p/14219620.html
那我们今天就到这里，新年快乐！
参考资料：
- https://en.wikipedia.org/wiki/24_Game
- 例题选自 University of Toronto, ESC180 2020 Final, Question 4 & Question 5