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

Question

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

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

虽然有类似问题appears to have been asked before , 但逻辑上的不同足以保证一个新线程。

参数: 给出总数以及整数列表。 整数可以任意组合(例如 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 编写代码，但任何语言的伪代码、指针或语法都很棒。傲慢地 mock 我缺乏数学能力也很酷；)

提前致谢!

Answer 1

我刚刚回答了这个问题，但它被错误地迁移到另一个 stackexchange 站点:https://codegolf.stackexchange.com/questions/3019/getting-an-answer-from-a-string-of-digits/3027#3027

Is there a classification for this type of exercise? (e.g. subset-sum, etc.)

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

---

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

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

使用 How to print all possible balanced parentheses for an expression?我们可以这样写:

#!/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)))