算法练习：4张牌凑24点

题集 , 评论

　　今天想和大家讨论的是一道我从这学期cs的期末考试得到灵感的题：Get 24 Poker Game。说到 Get 24 Poker Game，也就是我们通常说的凑24点，大家可能都比较熟悉。但是因为这个游戏有很多变种，我们还是来简单说一下游戏的规则。老规矩，上Wikipedia：

The 24 Game is an arithmetical card game in which the objective is to find a way to manipulate four integers so that the end result is 24.

　　简单来说，这个游戏需要玩家快速用随机抽出的四张牌上的整数通过常见的加减乘除计算来凑出24点来取得胜利（一定要用全4张，不可以弃牌）。不同于我们通常玩的斗地主，钓鱼等等扑克游戏，凑24点更考验玩家的数学反应能力（less fun but somewhat interesting:)）。在这里稍稍跑一下题，因为可能会有人好奇，为什么恰恰选了24这个数字。其实答案很直白，因为这个数字最容易被凑出来：24是拥有八个除数的最小整数(1, 2, 3, 4, 6, 8, 12, and 24），使用这个数字不仅仅把游戏变得更加简单（毕竟可能没有人想花一个小时在用扑克牌凑数上），还把游戏作废（目标数字凑不出来）的几率降到最小。

第一部分的大意是写出一个函数，让其能够以列表的形式接收四个数字并试图用加减乘除的方法来凑出目标点数（注意，这里不包括括号操作）。

第二部分相对于前一部分难度更高一点，要求写出函数，让其能够接受四个数字，并可通过对其进行加减乘除（这里包括括号）的操作来凑出目标点数。

　　通过读题，我们可以发现第一题和第二题最主要的差别在以下两点上：

  1. 第一题只需要考虑四个数字，三个符号的排列组合。
  2. 第二题需要考虑到一个，或者多个括号的算法，在这种情况下，我们不能直接计算结果，因为没有办法确定括号的个数和位置。

　　第一部分我们可以从运算式子的结构入手。正常写出的话，一个有四个运算数字的式子会长这个样子：

$${1+2+3+4}$$

结构一目了然，四个数字，三个运算符号。如果想生成所有排列组合的可能性的话，我们可以用嵌套for循环很容易的用代码实现如下：

1
2
3
4
5
6
7
def get_all_comb(num_list):
    for op_1 in ['+','-','*','/']: # 用第一个for loop来考虑所有第一个位置的运算符号的可能性
        for op_2 in ['+','-','*','/']: # 用第二个for loop来考虑所有第二个位置的运算符号的可能性
            for op_3 in ['+','-','*','/']: # 用第三个for loop来考虑所有第三个位置的运算符号的可能性
                # 构造一个字符串
                comb = str(num_list[0])+op_1+str(num_list[1])+op_2+str(num_list[2])+op_3+str(num_list[3]) 
                print(comb) # 打印运算式

　　这段代码的输出结果为 ‘1+2+3+4’，‘1+2+3-4’，‘1+2+3*4’…等等六十四个不重复的运算式。但是我们还要考虑到所有数字的排列组合的情况，注意在以上的例子里，所有运算的数字是没有变化的，但数字位置的变化在多数情况下会对运算结果造成影响，也就是说在我们改变运算符号的同时，我们也要考虑到所有数字的排列情况。

　　同样，我们也可以用以上相似的嵌套循环逻辑来用代码实现：

1
2
3
4
5
6
7
8
9
def get_num_comb(num_list):
    all_comb = [] # 准备收集所有排列组合
    for i in range(4): # 三个嵌套for循环分别对应在num_list里的序数
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    # 确定没有重复元素
                    if i != j and i != k and i != l and j != k and j != l and k != l:
                        print([num_list[i], num_list[j], num_list[k]]) #打印最终结果

　　但是我们可以通过以上两段代码发现，在这里用for loop来分别实现符号和数字的排列组合虽然是可行的（同理我们也可以用类似的for loop结构来），但却无法延伸到这道题的局限外，也就是说，这个思路仅限于这道题的Part 1，如果要做第二部分的话，我们需要重新写这部分的函数（这也是这两道题的第一个主要差别：数字数量的不确定性）。

　　为了使第一部分的解法可以延伸到第二题，我们需要换个思路。很自然的，为了解决数字数量的不确定问题，我们不能够再使用for loop这种需要定量条件的方法，而是使用递归（recursion）。

　　以上我们讨论到的两个问题，运算符号以及运算数字的排列组合，可以被分别写作两个递归函数。比起普通循环，递归函数的结构更加复杂。为了减少码代码时出现不必要的概念不清的错误，我们可以针对每个递归画出树形图来作结构分析。

　　我们先来看运算符号的递归规律，如果我们有三个需要考虑的运算位置的话，树形图便如下图：

24点_递归树形图.png

　　通过观察，我们可以看到第一层有4个分支，第二层有16个，第三层有64个。不难看出，这个递归规律的复杂度是随着递归的深度而以二次增长，所以可以用Big-Oh Notation表达成 O(4^n)，n为运算符号的个数。（关于运算复杂度和常见algorithm会有后续文章跟进，在这里不做过多解释）

根据以上基础结构，我们可以用代码来写出生成运算符号的递归函数，如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def generate_permutated_list(num_list):

    # 建立base case
    if len(num_list) == 0:
        return [] # 当n为0时不返回任何数字
    if len(num_list) == 1:
        return [num_list] # 当n为1时返回所有式子，作为之后首数字的基础
    list_of_comb = [] # 新建列表来存更新的排列
    for i in range(len(num_list)):
        first_num = num_list[i] # 生成首字母
        for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，继续递归
            list_of_comb.append([first_num] + j) #加入新的list

    return list_of_comb # 最后返回最终结果

　　如果再次检查运算复杂度，我们不难看出这个函数的复杂度符合我们的预测，为O(4^n)。

　　好了，我们再来看数字的排列方法。如果想要找到固定数量的数字的所有排列方式，我们需要用到permutation的逻辑：找到所有排列（长度为n）的第一个元素，然后根据每个元素找到剩余数字的第一个元素（剩余数字排列长度为n-1），以此类推，直到最后只剩余一个数字。我们来看一下这个递归思路的树状图（此树状图用了长度为三的list为例）：

24点_递归树形图2.png

　　递归的第一层有三个元素，第二层有3_2=6个元素，第三层有3_2*1=6个元素，我们可以看出这个逻辑的复杂度为 O(n!), n为需要排列组合数字的个数。

Permutation的逻辑比运算符号的排列稍稍复杂，但是我们可以用类似的递归结构来解决不同的问题，代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def generate_permutated_list(num_list):
    # 建立base case
    if len(num_list) == 0:
        return [] # 当n为0时不返回任何数字
    if len(num_list) == 1:
        return [num_list] # 当n为1时返回所有式子，作为之后首数字的基础
    list_of_comb = [] # 新建列表来存更新的排列
    for i in range(len(num_list)):
         first_num = num_list[i] # 生成首字母
         for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，继续递归
           list_of_comb.append([first_num] + j) #加入新的list

    return list_of_comb # 最后返回最终结果

　　分别生成数学操作符号以及所有数字的排列组合后，我们要把两个组合整合起来，以此生成所有的排列可能性。因为这里我们不用考虑排列组合数列的不确定性的问题（每个排列的长度，以及每组数学操作符号的长度维持不变），我们可以用循环的思维来生成所有数学表达式（所有数字和数学操作符号的组合）。但是生成所有数学表达式还不能完整的解决这个问题，因为我们不仅仅要生成所有的数学表达式，还要把表达式估值并和最终的目标数字进行比较。所以在组合最终的函数之前，我们需要先写一个估值函数来方便之后的使用。

　　估值函数的难点在于数学操作符号的处理，因为在数学表达式里这些运算符号都是以字符串的形式表达，例如 ‘+’，‘-’，所以无法当作正常运算符号放到代码中来操作。所以在这个情况，我们要重新赋予这些字符串它们象征的含义，代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def modify_op(equation, op):
    '''this function modify the given equation by only computing the section with the given operators
    parameters:
        equation: a list that represents a given mathematical equation which may or may not contain the 
                given numerical operators. Ex, ['1','+','2'] represents the equation 1+2
        op: a string that is the given numerical operators'''

    # 这里我们把代表数学计算的字符串和以上定义的操作函数的名字以字典的方式联系并储存起来
    operators = {'/':division, '*':multiply, '+':add, '-':subtract}

    while op in equation: # 用while循环来确保没有遗漏任何字符
        i = equation.index(op) # 找到表达式内的第一处需要计算的字符位置
        if op == '/' and equation[i+1] == '0': # 考虑除法操作的被除数为0的情况
             return ['']
         # 把表达式需要计算的部分替换成计算结果
         equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] 
            # 注意这里调用了前面字典里储存的函数名
     return equation # 返回结果

def evaluate(equation):
    '''return the evaluated result in float for the equation'''

    for op in ['/','*','+','-']: # 这里需要注意标点顺序，除在最先，因为需要考虑特殊情况，乘其次，然后才是加减
        equation = modify_op(equation, op) # 使用helper function
    return equation[0] # 最后返回最终计算结果

　　这里我们需要注意，这个估值函数能够接收表达式的形式为list，而list里的每项也必须要用字符串的形式来表达。

　　最后，我们只要按照之前提到的思路，整合表达式，并用以上估值函数来计算表达式的值，就可以完成这道题。在给出完整代码之前，我们再来最后复习一下这道题的解题思路：

  1. 找出所有加减乘除的排列组合
  2. 找出所有数字的排列组合
  3. 整合所有表达式可能
  4. 用估值函数计算表达式
  5. 对比表达式答案和目标数
  6. 返回符合要求的表达式

FLYY夜静风铃响佩环,\n秋声吹彻凤凰山。

个人简介。