评估随机长度的表达式

Question

以下是关于这个问题的翻译：

这个问题的基础在这里：

输入格式

第一行包含一个整数n，表示列表中元素的数量。第二行包含n个以空格分隔的整数a1, a2, a3, ...，表示列表的元素。

输出格式

打印一行内容为所需表达式的单个行。您可以在运算符和操作数之间插入空格。

注意

• 不允许对列表进行排列。
• 所有运算符具有相同的优先级并且是左结合的。

在我的下面的代码中，当我知道输入的长度时，可以使用嵌套的for循环使其正常工作，但是我的输入可能有5个、50个或500个元素，直到运行时我才知道这一点。嵌套的for循环的深度将是len(arr)-1，但也许有更好的方法来解决这个问题。

我认为我需要:

• 为随机长度的input_ints生成ops_combos（不使用permutations库，根据hackerrank的说明）
• 求解表达式
• 并返回第一个求值为True的表达式。

有什么建议吗？

import operator
ops = { "+": operator.add, "*": operator.mul, "-": operator.sub } # etc.

opers = ['+','*','-']
arr = [55, 3, 45, 33, 25] # needs to work for any length of arr

# Generate every len(arr)-1 combo of the 3 symbols (include repetition)
for i in range(3):
    for j in range(3):
        for k in range(3):
            for l in range(3):                
                x = ops[ opers[i] ]( arr[0], arr[1] )   # first number (0), first operator  (i), second number (1)
                x = ops[ opers[j] ]( x,      arr[2] )   # x,                second operator (j), third number  (2)
                x = ops[ opers[k] ]( x,      arr[3] )   # x,                third operator  (k), fourth number (3)
                x = ops[ opers[l] ]( x,      arr[4] )   # x,                fourth operator (l), fifth number  (4)

                if x % 101 == 0:
                    print (arr[0], opers[i], arr[1], opers[j], arr[2], opers[k], arr[3], opers[l], arr[4])

- Karl Baker

---

指令是不要对列表进行排列，也不要避免在运算符上使用排列函数，这是你必须做的。 - Olivier Melançon

感谢您的编辑，@OlivierMelançon。我看到我误解了指示。关于在运算符上使用排列，我是否正确理解，我需要使用“组合”而不是“排列”，以便允许重复？ - Karl Baker

@OlivierMelançon，忽略我上面评论中的问题。我在你下面的解决方案中看到你没有使用itertools的排列或组合。 - Karl Baker

Answer 1

您提供的链接并未禁止使用 itertools，这意味着您不能更改所提供数字的顺序。

也就是说，您需要使用itertools.product或自己实现的product方法，因为要获得解决方案需要测试所有可能的运算符组合。

函数find_operations返回所有解决方案的生成器。这使得可以使用next获取第一个解决方案或解压缩所有解决方案。

代码：

from itertools import product, chain
from operator import add, sub, mul

def apply(numbers, operations):
    """Return the result of applying a list of operations to the list of numbers"""
    ans, *numbers = numbers
    for num, op in zip(numbers, operations):
        ans = op(ans, num)

    return ans

def find_operations(numbers):
    """Return the equation as string that satisfies the res % 101 == 0"""

    # Pair operations and their symbol to later format the result
    operations = {add: '+', sub: '-',  mul: '*'}

    # Loop over all combinations of operations and break when one satisfies
    for ops in product(operations, repeat=len(numbers) - 1):
        if apply(numbers, ops) % 101 == 0:
            # The following lines are just formatting and are not the main focus
            ops = [operations[op] for op in ops]
            nums = [str(x) for x in numbers]

            yield ' '.join(chain(*zip(nums, ops), nums[-1:]))

例子

solutions = find_operations([22, 79, 21])

print(next(solutions))

输出

22 + 79 * 21

- Olivier Melançon

---

这种做法忽略了运算符的优先级。它把 22 + 79 * 21 计算为 (22 + 79) * 21，结果为 0 mod 101，但是 22 + (79 * 21) 的结果为 65 mod 101。我无法看出问题所在，因此无法确定是否可接受。 - Dan D.

@DanD。这个问题明确要求忽略运算符优先级。 - Olivier Melançon

@DanD。这里已经完成了，您可以阅读我从问题中提取的行，这些行指示所有操作具有相同的优先级。 - Olivier Melançon

@OlivierMelançon，这太棒了！我已经在几个输入数据集上测试过了，现在我正在逐步调试以弄清它是如何工作的。非常感谢您清晰而详尽的回答。 - Karl Baker

@neigedoi 不客气。如果这个答案解决了你的问题，请将其标记为已接受，以便未来的用户更容易找到它。 - Olivier Melançon

Answer 2

我认为不使用排列库似乎不太合理。但是您可以通过使用生成器来实现嵌套循环的等效操作：

opers = ['+','*','-']
arr = [55, 3, 45, 33]

def iterate(previous_iterator):
    for previous_list in previous_iterator:
        for oper in opers:
            yield [oper] + previous_list


operator_iterator = [[]]
for i in range(len(arr) - 1):
    operator_iterator = iterate(operator_iterator)

print(list(operator_iterator)) 
# [['+', '+', '+'], ['*', '+', '+'], ['-', '+', '+'], ['+', '*', '+'], ['*', '*', '+'], ['-', '*', '+'], ['+', '-', '+'], ['*', '-', '+'], ['-', '-', '+'], ['+', '+', '*'], ['*', '+', '*'], ['-', '+', '*'], ['+', '*', '*'], ['*', '*', '*'], ['-', '*', '*'], ['+', '-', '*'], ['*', '-', '*'], ['-', '-', '*'], ['+', '+', '-'], ['*', '+', '-'], ['-', '+', '-'], ['+', '*', '-'], ['*', '*', '-'], ['-', '*', '-'], ['+', '-', '-'], ['*', '-', '-'], ['-', '-', '-']]

你可以使用这个迭代器来找到你的解决方案：

import operator
ops = { "+": operator.add, "*": operator.mul, "-": operator.sub } # etc.

opers = ['+','*','-']
arr = [55, 3, 45, 33, 25] # needs to work for any length of arr

def iterate(previous_iterator):
    for previous_list in previous_iterator:
        for oper in opers:
            yield [oper] + previous_list
operator_iterator = [[]]
for i in range(len(arr) - 1):
    operator_iterator = iterate(operator_iterator)

for operator_list in operator_iterator:
    x = arr[0]
    for operator, value in zip(operator_list, arr[1:]):
        x=ops[operator](x, value)
    if x % 101 == 0:
        print(operator_list)

        # ['*', '+', '-', '+']
        # ['+', '-', '*', '-']

- Gelineau