在分配律和交换律下找到等效结果

Question

我有一个脚本，它循环 5 个数字向量，并将它们与所有四个操作混合，搜索给出特定目标数字结果的组合。

该脚本打印如下输出：

312 / 130 x 350 - 122 + 282 = 1000.0
312 / 130 x 350 + 282 - 122 = 1000.0
312 - 282 x 372 / 15 + 256 = 1000.0
142 + 350 - 372 x 125 / 15 = 1000.0
142 + 350 - 372 / 15 x 125 = 1000.0
350 / 130 x 312 + 282 - 122 = 1000.0
350 + 142 - 372 x 125 / 15 = 1000.0

每行均由数字列表和操作列表格式化。

我想做的是删除等效结果，即输出如下：

312 / 130 x 350 - 122 + 282 = 1000.0
312 - 282 x 372 / 15 + 256 = 1000.0
142 + 350 - 372 x 125 / 15 = 1000.0

作为解决方案，首先，我考虑“记住”已经给出 1000 的数字并跳过那些，但后来我意识到这可能会影响新的结果，所以我不知道该怎么办。

如何找到分配律和交换律下的等价结果？

注意：在显示的输出中，括号未显示，但顺序类似于reduce，这意味着，例如：

142 + 350 - 372 x 125 / 15 = 1000.0

计算如下：

(((142 + 350) - 372) x 125) / 15 = 1000.0

---

这是我到目前为止的代码：

import operator
from itertools import permutations, product, count
from functools import reduce

vectors = [[87, 125, 209, 312],
           [29, 122, 254, 372],
           [15, 130, 277, 369],
           [142, 197, 282, 383],
           [64, 157, 256, 350]]

OPER = {operator.add: '+', operator.sub: '-', operator.mul: 'x', 
        operator.truediv: '/'}

def format_result(nums, ops, res):
    s = ' '.join('{} {}'.format(n,OPER[op]) for n,op in zip(nums, ops))
    s += ' {} = {}'.format(nums[-1], res)
    return s

def calc(vectors, test=lambda x: x == 1000.):
    for vv in permutations(vectors):
        for indexes in product((0,1,2,3), repeat=5):
            numbers = tuple(v[i] for i,v in zip(indexes, vv))
            for operations in permutations(OPER):
                res = reduce(lambda x,y,n=count(0): operations[next(n)](x,y),
                             numbers)
                if test(res):
                    print(format_result(numbers, operations, res))

calc(vectors)

Answer 1

我认为可以通过根据对操作数执行的操作对操作数进行分组来解决该问题。示例：

312 / 130 x 350 + 122 + 282   => (/, [312, 130]), (x, [350]), (+, [122, 282])

然后，您可以对这些组的顺序施加某些限制：

1. - 组不能直接出现在 + 组之前
2. / 组不能直接出现在 + 组之前 每个组内的* 组
3. ，数字的顺序必须是升序

因此，可能的分组如下所示：

• “前 3 个 asc。操作数与 + 连接，然后是 2 个 asc与 a 连接的操作数*"
• “第一个操作数与 + 连接，然后 2 个操作数与 * 连接，然后 2 个操作数连接。与/”

不可能是这样的：

• “前2个asc与-连接，然后3个asc与+连接。 ” （会与“前 3 个 asc. 操作数与 + 连接，然后 2 个 asc.操作数与 - 连接）发生冲突

我尝试了一种强力方法来创建和填充此类分组，但它慢得难以忍受。也许你可以优化它以提高效率:)也可能是那里有一些微妙的错误，但不幸的是我没有更多的时间来处理它：

import operator
import fractions
from itertools import permutations, product, count
from functools import reduce

vectors = [[87, 125, 209, 312],
           [29, 122, 254, 372],
           [15, 130, 277, 369],
           [142, 197, 282, 383],
           [64, 157, 256, 350]]
vectors = [[fractions.Fraction(x) for x in v] for v in vectors]

operators = {
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    '/': operator.div,
    }

def create_groupings(n, exclude = ()):
  if n <= 0: yield ()
  for i in range(1, n+1):
    if not '+' in exclude:
      for rest in create_groupings(n - i, ('+',)):
        yield ((i, '+'),) + rest
    if not '-' in exclude:
      for rest in create_groupings(n - i, ('+', '-')):
        yield ((i, '-'),) + rest
    if not '*' in exclude:
      for rest in create_groupings(n - i, ('*',)):
        yield ((i, '*'),) + rest
    if not '/' in exclude:
      for rest in create_groupings(n - i, ('/', '*')):
        yield ((i, '/'),) + rest

def fill_grouping(groups, vectors):
  if len(groups) == 0:
    yield ()
    return

  (group_size, op), grest = groups[0], groups[1:]
  for vv in permutations(vectors):
    vecs, vrest = vectors[:group_size], vectors[group_size:]
    for operands in map(list, product(*vecs)):
      # enforce ascending ordering to avoid collisions
      # like A + B == B + A
      if operands != sorted(operands): continue
      for rest in fill_grouping(grest, vrest):
        yield ((op, operands),) + rest

groupings = create_groupings(5)
for g in groupings:
  for groups in fill_grouping(g, vectors):
    evaluated = ((op, reduce(operators[op], x)) for (op, x) in groups)
    _, value = reduce(lambda (_, x), (op, y): (None, operators[op](x,y)), evaluated)
    if 1000 == value:
      print groups

希望这有帮助（在至少这个想法:)