python - 在分配律和交换律下找到等价结果

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. 操作数与 * 连接”
• “第一个asc.操作数与+连接，然后2个asc.操作数与*连接，然后2个asc.操作数与/<连接”

不可能是这样的:

• “前 2 个 asc. 操作数与 - 连接，然后 3 个 asc. 操作数与 + 连接”(会与“前 3 个 asc. 操作数与 a 连接”发生冲突+，然后是-
连接的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

希望这会有所帮助(至少是想法:)