如何在Python中从数组元素中找到所有可能的计算结果,从而得到所需的数字? [已关闭]

问题描述 投票:0回答:3

我有一个数字数组,我想使用基本算术运算(加法、减法、乘法和除法)找到所有可能的计算,从而得到所需的数字。

例如,给定输入数组

[2, 1, 4, 6, 7]
和所需结果
3
,该函数应返回:

  • 2 + 1 = 3
  • 7 - 4 = 3
  • 6 / 2 = 3

这是我想出的一个基本实现:

def find_calculations(arr, target):
    results = []
    operations = ['+', '-', '*', '/']

    for i in range(len(arr)):
        for j in range(len(arr)):
            if i != j:
                a, b = arr[i], arr[j]
                for op in operations:
                    if op == '+':
                        if a + b == target:
                            results.append(f'{a} + {b} = {target}')
                    elif op == '-':
                        if a - b == target:
                            results.append(f'{a} - {b} = {target}')
                    elif op == '*':
                        if a * b == target:
                            results.append(f'{a} * {b} = {target}')
                    elif op == '/':
                        if b != 0 and a / b == target:
                            results.append(f'{a} / {b} = {target}')
    return results

# Example usage
arr = [2, 1, 4, 6, 7]
target = 3
output = find_calculations(arr, target)
print(output)

上面示例的输出是:

['2 + 1 = 3', '7 - 4 = 3', '6 / 2 = 3']

限制:

  • 输入数组可以包含任何整数。
  • 想要的结果也是一个整数。
  • 可以使用数组中任意多个整数。目标是尽快摆脱它们
  • 每次计算中最多可以使用数组的每个元素一次。

如何改进或优化此函数以处理更大的数组或更复杂的情况?

algorithm combinations combinatorics calculation number-systems
3个回答
1
投票

您想要做的是评估所有可能的计算并找到导致正确结果的选项。

构建它的一种简单方法是实现 RPN 计算(反向波兰表示法)。 https://en.wikipedia.org/wiki/Reverse_Polish_notation

基本上你要做的就是枚举数字和运算符的堆栈,这样你总是比运算符多一个数字。


0
投票

我认为这是一个有趣的问题,所以我决定演示如何有效地完成它。 在我的系统上,大约需要半秒才能找到所有 4193 个解决方案。

诀窍是使用动态编程来构建一个数据结构,从中可以有效地找到所有表达式。

from fractions import Fraction

def bit_subset(index, things):
    i = 0
    bit = 1
    answer = []
    while bit <= index:
        if bit & index:
            answer.append(things[i])
        i += 1
        bit += bit
    return answer

def indexes_to_bit_subset(indexes):
    answer = 0
    for index in indexes:
        answer += 2**index
    return answer

def calculation_tree (digits):
    # Here is the tree structure:
    #
    #   By bit_integer of subset used
    #     By value reached
    #       [
    #          count_of_ways,
    #          [
    #              [
    #                  count,
    #                  first subset bit_integer,
    #                  first value,
    #                  op ('+', '-', '*', '/', None),
    #                  second subset bit_integer (may be 0),
    #                  second value (may be None)
    #               ]
    #          ]
    #       ]
    #
    tree = {}

    # Populate with all of the raw numnbers.
    for i in range(len(digits)):
        # By bit_integer for 1 thing.
        tree[2**i] = {
            # By value reached (use fractions to avoid roundoff
            Fraction(digits[i], 1): [
                # Just 1 way to do it.
                1,
                # What are the ways?  Let me tell you!
                [[1, 2**i, digits[i], None, 0, None]]
                ]
            }

  # This loops over all subsets with something in the first.
    for subset_index in range(1, 2**len(digits)):
        # The indexes into the chosen subset.
        index_subset = bit_subset(subset_index, list(range(len(digits))))
        if subset_index not in tree:
            subtree = {}
            tree[subset_index] = subtree

            # Look at ways to split it with something in both sides
            for sub_subset_index in range(1, 2**len(index_subset)-1):
                co_subset_index = 2**(len(index_subset)) - 1 - sub_subset_index

                # We have a split by indexes into index_subset.
                # We need to turn that into a split by indexes into digits
                # Which we represent by integers representing bits.
                index_sub_subset = bit_subset(sub_subset_index, index_subset)
                sub_subset_bit_index = indexes_to_bit_subset(index_sub_subset)

                index_co_subset = bit_subset(co_subset_index, index_subset)
                co_subset_bit_index = indexes_to_bit_subset(index_co_subset)

                # Let's pull out the already known calculation results.
                subtree1 = tree[sub_subset_bit_index]
                subtree2 = tree[co_subset_bit_index]
                for value1 in subtree1.keys():
                    count1 = subtree1[value1][0]
                    for value2 in subtree2.keys():
                        count2 = subtree2[value2][0]
                        # We now have to add each possible operation result to subtree
                        options = {
                            '+': value1 + value2,
                            '-': value1 - value2,
                            '*': value1 * value2,
                        }
                        if value2 != 0:
                            options['/'] = value1 / value2

                        for op, value in options.items():
                            if value in subtree:
                                subtree[value][0] += count1 * count2
                                subtree[value][1].append([
                                    count1 * count2,
                                    sub_subset_bit_index,
                                    value1,
                                    op,
                                    co_subset_bit_index,
                                    value2
                                ])
                            else:
                                subtree[value] = [
                                    count1 * count2,
                                    [[
                                        count1 * count2,
                                        sub_subset_bit_index,
                                        value1,
                                        op,
                                        co_subset_bit_index,
                                        value2
                                    ]]
                                ]

    return tree

# Yields the expressions that result in value
def expression_iter (tree, bit_integer, value):
    if bit_integer in tree:
        subtree = tree[bit_integer]
        if value in subtree:
            ways = subtree[value][1]
            for (
                    count,
                    bit_integer1, value1,
                    op,
                    bit_integer2, value2
            ) in ways:
                if op is None:
                    yield str(value1)
                else:
                    for expr1 in expression_iter(tree, bit_integer1, value1):
                        for expr2 in expression_iter(tree, bit_integer2, value2):
                            yield f'({expr1} {op} {expr2})'

def all_expressions(digits, target):
    tree = calculation_tree(digits)
    frac_target = Fraction(target, 1)
    for bit_integer, subtree in tree.items():
        if frac_target in subtree:
            for expr in expression_iter(tree, bit_integer, frac_target):
                yield expr


for expr in all_expressions([2, 1, 4, 6, 7], 3):
    print(expr)

-1
投票

我认为你可以做的是你可以使用 rng 让它生成随机数
模块。让他们在有理数范围内做随机数,并对其进行随机运算。如果方程等于某个数字,则打印方程。你还可以制作一个类似人工智能的简单东西,设置随机数的合理范围以使其更快。 (注意/编辑,随机范围选择一个数字,并将该数字转换为输入数字之一。)

示例

# simple 2 digit example
import random
array = [2, 5, 6, 1]
c = 1
wantedresult = 7
while c == 1:
  i = random.randint(0, 4)
  a = random.randint(0, 4)
  numa = array[i]
  numb = array[a]
  answer = numb - numa 
  if answer == wantedresult:
    print(numb + " - " + numa)
  answer = numb + numa 
  if answer == wantedresult:
    print(numb + " + " + numa)
  answer = numa + numb
  if answer == wantedresult:
    print(numa + " + " + numb
  answer = numa - numb
  if answer == wantedresult:
    print(numa + " - " + numb
© www.soinside.com 2019 - 2024. All rights reserved.