高效算法，可针对特定目标组成有效的表达式

高效算法，可针对特定目标组成有效的表达式

面对这种编程挑战，我首先尝试回答以下问题：

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

表示表达式

看起来像小型编程语言的问题往往使我想到Lisp。问题是要求我们生成系列：

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

基本上在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

是一个很大的数字，从这一点来看，任何表达式甚至都能够得到just的结果

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' ->

每个待处理状态都被推送到一个列表，并且每次循环时都会d出当前要考虑的状态。从最后的状态继续，接下来的可能性是再次移动标记，并分割数字以形成三个表达式之一。

        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))

通过存储有关 *** 作的更多信息，而不仅仅是执行它们的功能，可以通过多种方法来解决。对于这个问题，这并不是真正需要的，其他可能的转换也不是必需的，例如组合多个表达式或排除不相关的部分。

最后的实现说明，很困难，我将迭代的方向和（最初）表达式的布局都向后。