algorithm - 查找所有可能的计算以获得所需的数字

Question

是否有任何函数可以接受输入（数字数组）并在它们上找到所有可能的计算，从而产生所需的结果（数字）。

例如，如果 input 是2, 1, 4, 6, 7并且期望的结果是3。它会返回类似的东西。

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

Answer 1

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

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

基本上你要做的就是枚举一堆数字和操作符，这样你的数字总是比操作符多一个。

Answer 2

我认为这是一个有趣的问题，所以我决定演示如何有效地完成它。在我的系统上，找到所有 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)

Answer 3

我认为你可以做的是你可以使用 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