用特定目标组成有效表达式的高效算法

Question

问题表述为:给定一个仅包含数字0-9和目标值的字符串,返回通过在数字之间添加一些二元运算符(+, - 或*)创建的所有表达式,以便它们计算为目标值.在某些情况下,可能没有任何二进制运算符会创建有效的表达式,在这种情况下,该函数应返回一个空数组.新表达式中的数字不应包含前导零.

该函数应返回所有评估为目标的有效表达式,按字典顺序排序.

例如:

digits = "123"和target = 6,应该返回: ["1*2*3", "1+2+3"]

我目前的算法如下.它有点慢,所以我正在寻找一种更有效的方法来解决问题.我目前的算法产生操作数和运算符的所有组合.对于上面的例子,它产生了

操作数:

[['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]

运营商:

{0: [()], 1: [('+',), ('-',), ('*',)], 2: [('+', '+'), ('+', '-'), ('+', '*'), ('-', '+'), ('-', '-'), ('-', '*'), ('*', '+'), ('*', '-'), ('*', '*')]}

然后它结合了操作数和运算符的所有可能组合并评估每个.

数字有一个约束,2 ? digits.length ? 10. 所以它并没有那么糟糕,但是这个算法对于一个长度为10的数字需要大约4.3秒,其中它应该只需要4秒(最大值).

我还尝试使用以下替代方法加速eval()函数:

if eval(temp) == target:

要么

exp_as_func = eval('lambda: ' + temp)
if exp_as_func() == target:

要么

compiled = compile(temp, '<string>', 'eval')
if compiled == target:

所有这些仍然需要使用Python 3大约相同的时间.

码:

import itertools
import time

def getValidExp(digits, target):    
    def getSign_combination(length):
        signCombo = {}
        for i in range(0, length):
            signCombo[i] = [c for c in itertools.product(('+', '-', '*'), repeat=i)]
        return signCombo

    def generate_combination(source, comb):
        res = []
        for x, action in zip(source, comb + (0,)):      
            res.append(x)
            if action == 0:
                #####IF ITS A 0, YIELD STRING.  IF NOT COMBINE NEXT ONE
                yield "".join(res)
                res = []


    #####PRODUCT GENERATES (0,0,1).  ALL COMBINATIONS.  0 MEANS BY ITSELF, 1 APPEND NEXT ITEM.

    elementCombo = [list(generate_combination(digits, c)) for c in itertools.product((0, 1), repeat=len(digits) - 1)]

    signCombo = getSign_combination(len(digits))

    result = []
    for e in elementCombo:
        signs = signCombo[len(e)-1]

        for i,sign in enumerate(signs):

            temp = [ item for tple in zip(e, sign) for item in tple ]
            temp.append(e[-1])
            temp = "".join(temp)

            try:
                if eval(temp) == target:
                    result.append(temp)
            except:
                pass

    return sorted(result)

digits = "3456237490"
target = 9180
print("Answer:", getValidExp(digits, target))

使用计算器函数的代码(没有eval()),几乎具有相同的速度:

from itertools import combinations, permutations
import itertools
import time

def getValidExp(digits, target):

    def calculate(s):
        operands, operators = [], []
        operand = ""
        for i in reversed(range(len(s))):
            if s[i].isdigit():
                operand += s[i]
                if i == 0 or not s[i - 1].isdigit():
                    operands.append(int(operand[::-1]))
                    operand = ""
            elif s[i] == '*':
                operators.append(s[i])
            elif s[i] == '+' or s[i] == '-':
                while operators and operators[-1] == '*':
                    compute(operands, operators)
                operators.append(s[i])

        while operators:
            compute(operands, operators)

        return operands[-1]

    def compute(operands, operators):
        left, right = operands.pop(), operands.pop()
        op = operators.pop()
        if op == '+':
            operands.append(left + right)
        elif op == '-':
            operands.append(left - right)
        elif op == '*':
            operands.append(left * right)

    def getSign_combination(length):
        signCombo = {}
        for i in range(0, length):
            signCombo[i] = [c for c in itertools.product(('+', '-', '*'), repeat=i)]
        return signCombo

    def generate_combination(source, comb):
        res = []
        for x, action in zip(source, comb + (0,)):
            res.append(x)
            if action == 0:
                yield "".join(res)
                res = []

    start = time.clock()

    #####PRODUCT GENERATES (0,0,1).  ALL COMBINATIONS.  0 MEANS BY ITSELF, 1 APPEND NEXT ITEM.
    elementCombo = [list(generate_combination(digits, c)) for c in itertools.product((0, 1), repeat=len(digits) - 1)]

    signCombo = getSign_combination(len(digits))

    result = []
    for e in elementCombo:
        signs = signCombo[len(e)-1]
        for i,sign in enumerate(signs):
            temp = ""
            valid = True

            for num in e:
                if num[0] == '0' and len(num) > 1:
                    valid = False
                    break

            if valid:
                for num,operator in zip(e,sign):
                    temp += num
                    temp += operator

                temp += e[-1]

                ####USING CALCULATOR CODE
                if calculate(temp) == target:
                    result.append(temp)

    print(time.clock() - start)
    return sorted(result)


digits = "3456237490"
target = 9180
print("Answer:", getValidExp(digits, target))

Answer 1

有了这种编程挑战,我首先尝试回答这些问题:

• 如何表达表达方式？
• 我们可以减少可能的表达式数量吗？
• 我们可以为每个表达做更少的工作吗？

代表表达

看起来像小编程语言的问题往往让我想到Lisp.问题是要求我们生成系列:

123
(* 12 3)
(+ 12 3)
...
(- (- 1 2) 3)

基本上(operator, left, right)左右三元组的二进制表达式也可以是表达式.组件的顺序实际上并不重要.Python有元组,在operator模块中它有各种二进制操作的函数.所以,我打算用以下形式构建表达式:

(operator.sub, (operator.sub, 1, 2), 3)

然后可以使用(大多数)简单的递归函数来评估它:

def compute(expr):
    if isinstance(expr, tuple):
            op, left, right = expr
            return op(compute(left), compute(right))
    return expr

减少可能性

从问题描述来看,似乎每个数字都会有一个指数的可能表达式给出.我们可以通过创建所有排列来消除这些部分方式吗？

例如,输入六位数输入和目标结果5.在创建排列的过程中,假设从前四位数创建了以下表达式,剩下两个要处理:

(* 42 81) '??'

3696是一个很大的数字,从这一点来说,任何表达甚至能够得到一个结果5吗？我们可以完全跳过创建它们吗？

不幸的是,接近结尾的数字仍然可以做出重大改变:

(+ (* (* 42 81) 0) 5)

可能有一些我们可以避免的分支,但我们将不得不考虑大多数表达式.

减少工作量

好的,鉴于我们必须实际获得大量表达式的结果,还有其他方法可以省力吗？

让我们想象一下,我们通过生成一个序列的一部分,这三个最终表达式一个接一个地生成:

...
(* (- 8 (* 3 6)) 1)
(+ (- 8 (* 3 6)) 1)
(- (- 8 (* 3 6)) 1)
...

他们都给出了不同的结果,[12, 13, 11]但内心部分(- 8 (* 3 6))是相同的,而且永远都是12.我们的解决方案应该考虑利用这一点.

一个答案

对于任何需要剧透的人来说,我已经为初始实现设置了分支,从顶部计算每个表达式,一个记忆计算的次要变化,以及在生成表达式时预先计算结果的最终实现加上一些小的调整.

• 17.40s elapsed 6180k max mem 来自问题的原文
• 20.60s elapsed 6284k max mem 没有问题的评价
• 4.65s elapsed 5356k max mem 我最初的
• 2.71s elapsed 5316k max mem 我的回忆
• 1.50s elapsed 5356k max mem 我的预计算

关于我的实施的一些注释.该generate()函数通过考虑字符串中的每个点并创建可能的下一个状态来创建候选表达式.例如,在开始时,两者都移动标记,并拆分第一个数字:

'3|456237490' ->
    '34|56237490' -> ...
    3 '4|56237490' ->

每个挂起状态都被推送到一个列表,每次循环时都会弹出当前要考虑的状态.从最后的状态继续,下一个可能性是再次移动标记,并分割数字以形成三个表达式中的一个.

        3 '45|6237490' -> ...
        (* 3 4) '5|6237490' -> ...
        (+ 3 4) '5|6237490' -> ...
        (- 3 4) '5|6237490' -> ...

到目前为止,我已经使用运算符优先级来掩盖一个皱纹.处理乘法时,我们可能需要重写现有的表达式.考虑:

(+ 1 2) '3|' ->
    (* (+ 1 2) 3) '' # ???
    (+ (+ 1 2) 3) ''
    (- (+ 1 2) 3) ''

对于加法和减法,这很好,顺序无关紧要.但是,2 * 3必须在此之前发生1 + ....简而言之,我们需要推动内部的乘法:

(+ 1 2) 3 -> (+ 1 (* 2 3))

通过存储有关您的操作的更多信息,除了执行它们的功能之外,还有一些简单的方法可以解决这个问题.对于这个并非真正需要的问题,也没有其他可能的转换,例如组合多个表达式或分解出不相关的部分.

最后的实现说明,只是很困难我做了迭代的方向和(最初)表达式的向后布局.