算法演练----24点游戏

给定4个整数，数字范围在1~13之间任意使用+-*/（），构造出一个表达式，使得最终结果为24，

方法一 算法分析：加括号和取出重复表达式
# 导入精确除法模块，使得在Python2中除法运算的行为更接近Python3（Python3中除法默认是精确除法）
from __future__ import division
# 导入组合函数，用于生成给定元素的不同组合情况
from itertools import combinations
import re
import numpy as np# Solver类用于解决通过给定数字组合，利用四则运算及一些扩展运算来得到特定目标值（这里目标值默认为24）的问题
class Solver:# 定义目标值为24，即期望通过运算得到的结果target = 24# 定义可使用的运算符列表，包含常规四则运算以及扩展的重复减和重复除（'--'，'//'），虽然在常规数学中不太常见，但这里作为一种自定义运算来丰富组合可能性ops = ['+', '-', '*', '/', '--', '//']# 类的初始化方法，接收一个参数precise_mode（默认为False），用于控制是否精确处理运算表达式中的括号等细节def __init__(self, precise_mode=False):self.precise_mode = precise_mode# solution方法是主要的对外接口，用于寻找能得到目标值的表达式，接收一个数字列表nums作为参数def solution(self, nums):result = []# 调用dimensionality_reduction方法对输入的数字列表进行降维处理（简化数字和运算组合的复杂度），得到不同的分组情况groups = self.dimensionality_reduction(self.format(nums))for group in groups:for op in self.ops:# 调用assemble方法根据给定的两个表达式（或数字）和运算符构建一个新的表达式exp = self.assemble(group[0], group[1], op)['exp']# 调用check方法检查构建的表达式计算结果是否接近（在一定精度范围内）目标值，并且确保该表达式不在结果列表中（避免重复添加）if self.check(exp, self.target) and exp not in result:result.append(exp)# 将找到的满足条件的表达式添加等于目标值的后缀，例如 "表达式 = 24" 的形式return [exp + '=' + str(self.target) for exp in result]# dimensionality_reduction方法用于对输入的表达式（或数字）列表进行降维处理，尝试通过不同的组合和运算逐步简化def dimensionality_reduction(self, nums):result = []# 如果输入的列表长度大于2，说明还有多个元素需要进一步组合运算if len(nums) > 2:# 使用group方法对nums进行分组，每次取2个元素为一组for group in self.group(nums, 2):for op in self.ops:# 调用assemble方法将每组的两个元素根据当前运算符进行组合，得到一个新的元素（包含运算后的表达式和运算符信息），与剩余元素组成新的列表继续进行降维处理new_group = [self.assemble(group[0][0], group[0][1], op)] + group[1]result += self.dimensionality_reduction(new_group)else:# 如果列表长度小于等于2，直接返回该列表作为一种基本情况（无法再进一步分解组合了）result = [nums]return result# assemble方法根据两个表达式（或数字）以及运算符构建一个新的表达式，同时处理一些特殊情况（如交换律、括号添加等）def assemble(self, exp1, exp2, op):# 如果运算符是重复减或重复除，交换两个表达式的顺序并递归调用assemble方法，将运算符还原为单减或单除进行处理（因为重复减和重复除可能是自定义的一种处理逻辑，这里转换为常规运算来构建表达式）if op == '--' or op == '//':return self.assemble(exp2, exp1, op[0])# 如果运算符是乘或除，给两个参与运算的表达式都添加括号，以明确运算顺序（按照数学运算规则，乘除运算优先级高于加减，添加括号可以更准确地体现运算顺序）if op in "*/":exp1 = self.add_parenthesis(exp1)exp2 = self.add_parenthesis(exp2)# 如果处于精确模式（precise_mode为True），根据不同运算符进一步处理括号添加情况if self.precise_mode:if op == '-':exp2 = self.add_parenthesis(exp2)elif op == '/':exp2 = self.add_parenthesis(exp2, True)# 调用convert方法对构建好的表达式进行格式转换（可能涉及一些字符串处理，比如调整运算顺序等，具体看convert方法实现），得到最终的表达式字符串exp = self.convert(exp1['exp'] + op + exp2['exp'], op)return {'op': op, 'exp': exp}# add_parenthesis方法根据条件决定是否给表达式添加括号，用于明确运算顺序或者遵循精确模式的要求@staticmethoddef add_parenthesis(exp, is_necessary=False):# 如果满足必要添加括号的条件（比如is_necessary为True且表达式不是单纯数字，或者运算符是加减），则添加括号if (is_necessary and not exp['exp'].isdigit()) or exp['op'] in "+-":result = {'exp': '(' + exp['exp'] + ')','op': exp['op']}else:result = expreturn result# check方法用于检查给定的表达式计算结果是否在一定精度范围内接近目标值，同时捕获除零异常（因为在eval运算表达式时可能出现除数为0的情况）@staticmethoddef check(exp, target, precision=0.0001):try:# 使用eval函数计算表达式的值，然后判断与目标值的差值是否小于给定精度，若小于则认为接近目标值，返回Truereturn abs(eval(exp) - target) < precisionexcept ZeroDivisionError:return False# convert方法用于对表达式字符串进行格式转换，主要涉及根据运算符调整表达式中各部分的顺序等操作@staticmethoddef convert(exp, op):# 如果运算符是加减，定义一个正则表达式模式，用于匹配包含乘除运算或者数字的部分，然后在表达式前添加正号（可能是为了统一处理符号相关逻辑）if op in "+-":pattern = r'([\+\-]((\(.+\)|\d+)[\*\/](\(.+\)|\d+)|\d+))'exp = '+' + expelse:# 如果运算符是乘除，定义另一种正则表达式模式，用于匹配乘除运算和数字部分，然后在表达式前添加乘号（同样可能是为了统一处理逻辑）pattern = r'([\*\/](\(.+?\)|\d+))'exp = '*' + exp# 使用正则表达式查找所有匹配的部分，提取并排序后拼接成新的字符串，目的可能是为了对表达式中的各运算部分进行一种规范化整理result = ''.join(sorted([i[0] for i in re.findall(pattern, exp)]))if len(result)!= len(exp):result = expreturn result[1:]# format方法将输入的数字列表转换为包含表达式和空运算符的字典列表，方便后续统一处理（将数字视为一种简单的表达式形式）@staticmethoddef format(nums):return [{'op': ' ', 'exp': str(num)} for num in nums]# group方法用于将输入的表达式（或数字）列表按照指定数量进行分组，生成不同的分组组合情况@staticmethoddef group(exp_list, counter):index_list = [i for i in range(len(exp_list))]combination = list(combinations(index_list, counter))for group1 in combination:group2 = list(set(index_list) - set(group1))yield [[exp_list[g1] for g1 in group1],[exp_list[g2] for g2 in group2]]if __name__ == "__main__":# 定义一个变量auto_input用于控制是否自动生成输入数字，如果为True则自动生成随机数字作为输入，否则手动从用户输入获取数字auto_input = Falseif auto_input:# 使用numpy的随机数生成功能，生成4个范围在1到20之间的整数作为输入数字列表customer_input = np.random.randint(1, 20, size=4).tolist()else:customer_input = []customer_input.append(input('请输入第一个数字:'))customer_input.append(input('请输入第二个数字:'))customer_input.append(input('请输入第三个数字:'))customer_input.append(input('请输入第四个数字:'))# 创建Solver类的实例，使用默认的precise_mode（False）task = Solver()# 调用solution方法寻找能得到目标值的表达式answer = task.solution(customer_input)if len(answer) == 0:print('No solution')else:for a in answer:print(a)

第二种方案:列表切片操作实现排列组合
以下代码用于获取用户输入的四个数字，不过目前处于注释状态，如果要使用，取消注释即可
a = int(input("请输入第1个数字："))
b = int(input("请输入第2个数字："))
c = int(input("请输入第3个数字："))
d = int(input("请输入第4个数字："))
list1 = [a, b, c, d]# 定义四则运算的符号列表，包含加、减、乘、除四种符号，后续将通过这些符号的不同组合来构建表达式进行运算
symbols = ["+", "-", "*", "/"]# 外层的三个嵌套循环，用于遍历所有可能的运算符号组合
# 通过三重循环可以生成所有符号的排列情况，例如：先固定第一个符号，遍历第二个和第三个符号的所有可能组合，然后再更换第一个符号，重复此过程
for s1 in symbols:for s2 in symbols:for s3 in symbols:# 内层的四层嵌套循环，用于尝试所有数字的排列组合进行运算# 通过不断改变数字的排列顺序以及结合外层循环的符号组合，来穷举所有可能的四则运算表达式情况for i in range(4):# 取出当前排列中索引为i的数字，作为第一个参与运算的数字，赋值给oneone = list1[i]# 通过列表切片操作，获取除去当前索引为i的数字后的剩余数字列表，赋值给list2# 例如：如果i为0，那么list2就是[b, c, d]；如果i为1，list2就是[a, c, d]，以此类推list2 = list1[0:i] + list1[i + 1:]for j in range(3):# 从剩余数字列表list2中取出索引为j的数字，作为第二个参与运算的数字，赋值给twotwo = list2[j]# 再次通过列表切片操作，获取除去当前索引为j的数字后的剩余数字列表，赋值给list3list3 = list2[0:j] + list2[j + 1:]for k in range(2):# 从剩余数字列表list3中取出索引为k的数字，作为第三个参与运算的数字，赋值给threethree = list3[k]# 通过列表切片操作获取最后一个参与运算的数字，赋值给four# 例如：如果k为0，那么four就是list3[1]；如果k为1，four就是list3[0]four = (list3[0:k] + list3[k + 1:])[0]# 根据当前取出的数字和符号组合，构建一个四则运算表达式的字符串格式，后续将通过eval函数对其进行求值运算express = "(({0}{1}{2}){3}({4}){5}{6})".format(one, s1, two, s2, three, s3, four)try:# 使用eval函数对构建好的表达式字符串进行求值运算，eval函数会按照Python的运算规则解析并计算表达式result = eval(express)# 判断运算结果是否等于24，如果等于，则表示找到了满足条件的表达式if result == 24:# 输出找到的能得到24的表达式，并在表达式后面添加 " = 24" 进行标识，然后直接退出程序print(express + " = 24")# 找到结果为24的表达式后直接退出程序，避免继续不必要的循环计算exit(0)except ZeroDivisionError:# 捕获除零异常，因为在使用除法符号构建的表达式中，可能出现除数为0的情况，# 当出现这种情况时，捕获异常并跳过本次运算，继续尝试其他数字和符号的组合continue# 如果经过所有的数字排列组合和符号组合尝试后，都没有找到结果为24的表达式，则输出提示信息
print("无法算出")

#第三种itertools 模块实现排列组合
import itertools
import copy# 获取用户输入的四个数字
a = int(input("请输入第1个数字："))
b = int(input("请输入第2个数字："))
c = int(input("请输入第3个数字："))
d = int(input("请输入第4个数字："))
inputList = [a, b, c, d]listAll = []
listSignIndex = []
listSign = []
listSet = list(itertools.permutations(inputList, 4))
# 将生成的数字全排列结果转换为列表形式，并添加到listAll列表中，
# 这样listAll中就包含了输入的四个数字的所有不同排列情况
for i in listSet:listAll.append(list(i))# 该函数的功能是根据listSignIndex列表中的索引值，将对应的运算符号添加到listSign列表中
# 索引0对应 +，索引1对应 -，索引2对应 *，索引3对应 /
def changIndexToSign():for i in listSignIndex:if i == 0:listSign.append("+")elif i == 1:listSign.append("-")elif i == 2:listSign.append("*")elif i == 3:listSign.append("/")last = []# start函数用于尝试通过不同的运算组合（四则运算），利用输入的四个数字来得到结果为24的表达式
def start():global last# 遍历所有数字的排列情况（listAll列表中的每一组数字排列）for list1 in listAll:val = list1[0]  # 先取出当前排列的第一个数字作为初始值last = copy.deepcopy(list1)  # 深拷贝当前的数字排列，用于后续构建表达式字符串# 循环遍历四种运算符号，这里通过索引来对应不同的运算符号，0表示 +，1表示 -，2表示 *，3表示 /for i in range(4):if i == 0:val += list1[1]  # 如果索引为0，执行加法运算elif i == 1:val -= list1[1]  # 如果索引为1，执行减法运算elif i == 2:val *= list1[1]  # 如果索引为2，执行乘法运算elif i == 3:val /= list1[1]  # 如果索引为3，执行除法运算val2 = val  # 保存当前运算后的结果，用于内层循环结束后恢复值# 开始内层循环，再次遍历四种运算符号，用于对第三个数字进行运算for j in range(4):if j == 0:val += list1[2]elif j == 1:val -= list1[2]elif j == 2:val *= list1[2]elif j == 3:val /= list1[2]val1 = val  # 保存当前运算后的结果，用于最内层循环结束后恢复值# 最内层循环，同样遍历四种运算符号，用于对第四个数字进行运算for k in range(4):if k == 0:val += list1[3]elif k == 1:val -= list1[3]elif k == 2:val *= list1[3]elif k == 3:val /= list1[3]# 如果经过一系列运算后，结果等于24，则记录当前使用的运算符号索引if val == 24:listSignIndex.append(i)listSignIndex.append(j)listSignIndex.append(k)changIndexToSign()return  # 找到满足条件的组合后，直接返回，结束函数else:val = val1  # 如果结果不等于24，恢复到上一次内层循环运算后的结果，继续尝试其他运算符号val = val2  # 内层循环结束后，恢复到第二次运算后的结果，继续尝试其他运算符号val = list1[0]  # 外层循环每次开始时，恢复初始值，重新进行不同运算符号组合的尝试start()
listSign.append("")
lastStr = "(("
# 构建最终的表达式字符串，根据运算符号和数字的顺序进行拼接
for i in range(4):if i == 1 or i == 2:lastStr += str(last[i]) + ")" + listSign[i]else:lastStr += str(last[i]) + ")" + listSign[i]# 输出构建好的表达式字符串，并在末尾添加 =24，表示期望的结果为24
print(lastStr + "=24")输出结果：