给定数字列表，在使用 +-*/ 获得特定结果时保持数字顺序

Question

不确定以前是否有人问过这个问题，但找不到此类问题的具体提及。

这是子集和和背包的变体。

虽然类似的问题似乎之前已被问过，但逻辑足够不同，足以保证一个新的线程。

参数 ： 给出了总数以及整数列表。 整数可以以任意数量的方式组合（例如 1 2 3 = 12, 3 或 1, 23 或 1, 2 3） 允许 3 种运算：

• 1 加法
• 1 减法
• 1 除法

示例：

1 2 9 3 7 4 = 22

解决方案：

(129 - 3) / 7 + 4 = 22

此类练习有分类吗？ （例如子集和等）

一些想法：

1. 创建所有可能的数字组合的多维数组。 由于只允许使用 3 个运算符，因此该数组将包含 3 列/元素。

2. 在点 1、2 或 3 处随机插入运算符并进行暴力破解，直到找到解决方案。

这与优雅的解决方案相差甚远。
任何见解将不胜感激。

我可能会用 Perl 编写这个代码，但任何语言的伪代码、指针或语法都很棒。对我缺乏数学资金的傲慢嘲笑也很酷；）

提前致谢！

Answer 1

我刚刚回答了这个问题，但它被错误地迁移到另一个 stackexchange 站点：https://codegolf.stackexchange.com/questions/ 3019/从数字串中获取答案/3027#3027

这种类型的运动有分类吗？ （例如子集和等）

我将其称为查找列表的所有二元运算符“约简”，以任意顺序应用，使用运算符 +、-、*、/ 和 10a+b/concat

---

这是 Python 中的一种强力方法。在下面树中的每个节点，取左侧和右侧可能性的笛卡尔积。对于每一对，将所有运算符应用于它，以产生一组新的可能性。你必须小心不要这样做 (1-2)3 = -13;您可以通过创建 Digit 对象来解决此问题。

下面是加泰罗尼亚数字的图示，其中每个节点都是一个运算符。操作数量大致为 Catalan(#digits-1) * #operators^(#digits-1)。如果#digits=10那么应该只需要尝试大约十亿件事。

使用 如何打印表达式所有可能的平衡括号？ 我们可以这样写：

#!/usr/bin/python3

import operator as op
from fractions import Fraction
Fraction.__repr__ = lambda self: '{}/{}'.format(self.numerator, self.denominator)

Digits = tuple

operators = {op.add, op.sub, op.mul, Fraction}

def digitsToNumber(digits):
    """
        (1,2,3) -> 123
        123 -> 123
    """
    if isinstance(digits, Digits):
        return sum(d * 10**i for i,d in enumerate(reversed(digits)))
    else: # is int or float
        return digits

def applyOperatorsToPossibilities(left, right):
    """
        Takes every possibility from the left, and every
        possibility from the right, and takes the Cartesian
        product. For every element in the Cartesian product,
        applies all allowed operators.

        Returns new set of merged possibilities, ignoring duplicates.
    """
    R = set() # subresults
    def accumulate(n):
        if digitsToNumber(n)==TO_FIND:
            raise Exception(n)
        else:
            R.add(n)

    for l in left:
        for r in right:
            if isinstance(l, Digits) and isinstance(r, Digits):
                # (1,2),(3) --> (1,2,3)
                accumulate(l+r)
            for op in operators:
                #  12,3 --> 12+3,12-3,12*3,12/3
                l = digitsToNumber(l)
                r = digitsToNumber(r)
                try:
                    accumulate(op(l,r))
                except ZeroDivisionError:
                    pass

    return R

def allReductions(digits):
    """
        allReductions([1,2,3,4])
        [-22, -5, -4, -3, -5/2, -1/1, -1/3, 0, 1/23, 1/6, 1/5, 1/3, 2/3, 1/1, 3/2, 5/3, 2, 7/2, 4/1, 5, 6, 7, 9, 15, 23, 24, 36, 123]
    """
    for reduction in set.union(*associations(
            digits, 
            grouper=applyOperatorsToPossibilities, 
            lifter=lambda x:{(x,)})
            ):
        yield digitsToNumber(reduction)

TO_FIND = None
INPUT = list(range(1,4))
print(sorted(allReductions(INPUT)))

Answer 2

一种简单的暴力方法似乎效果很好。

让我们使用 RPN 来避免括号。将输入拆分为单个数字，并尝试在数字之间插入运算符（即：无、空格和算术运算符），直到结果字符串计算为目标值。

javascript 中的示例： http://jsfiddle.net/B5NdN/4 。我只是从 0 到 6^（输入长度​​）循环以获得所有可能的运算符组合，您的任务可能需要更复杂的东西，但原则仍然存在。