値と数学演算のリストの数式を見つける（またはブルートフォース）

Question

だから私はいくつかの値を含むリストを持っています。 [230, 67, 34, 60, 2, 10]
と、私が事前に知っている操作[operations.add, operations.sub, operations.mul, operations.div]とresult numberのリスト。

私に結果を与える可能なすべての数式を見つける最良の方法は何でしょうか。

たとえば、結果が154の場合、解決策の1つは60*2+34です。

私はこのアルゴリズムを設計する際に問題があります。これは、式にどの値と演算が使用されているかわからないためです。
Pythonコードをいくつか用意していただければ幸いです。
ありがとうございます。

Answer 1

可能なすべての組み合わせを表すツリーを作成できます。ここで、ノードは数値または演算子のいずれかを表します。次に、結果のツリーでDFSまたはBFSを実行することで、ルートからノードまでのパスによって表される式が目的の値になるように、すべてのノードを見つけることができます。

class Node(): 
    def __init__(self, type, val, parent, children): 
     self.type = type 
     self.value = val 
     self.parent = parent 
     self.children = children 
     self.total = None 


def expandBranch(node, numList, opList): 

    if len(numList) == 0: 
     return 

    if node.type == "Operator" or node.type is None: 
     for i in range(len(numList)): 
      newList = numList[:] 
      num = newList.pop(i) 
      newNode = Node("Number", num, node, []) 
      node.children.append(newNode) 
      expandBranch(newNode, newList, opList) 
    else: 
     for op in opList: 
      newNode = Node("Operator", op, node, []) 
      node.children.append(newNode) 
      expandBranch(newNode, numList, opList) 


def dfs(node, result): 

    if len(node.children) == 0: 
     return 

    if node.type == "Number": 
     if node.parent.type == None: 
      node.total = node.value 
     elif node.parent.value == "+": 
      node.total = node.parent.total + node.value 
     elif node.parent.value == "-": 
      node.total = node.parent.total - node.value 
     elif node.parent.value == "*": 
      node.total = node.parent.total * node.value 
     elif node.parent.value == "/": 
      node.total = node.parent.total/node.value 
     else: 
      pass # should never come here 
     if node.total == result: 
      output = [] 
      while node.parent is not None: 
       output.insert(0, node.value) 
       node = node.parent 
      print(output) 
      return 
    elif node.type == "Operator": 
     node.total = node.parent.total 
    else: 
     pass # root node, nothing to do 

    for child in node.children: 
     dfs(child, result) 


def main(): 
    nums = [230, 67, 34, 60, 2, 10] 
    ops = ["+", "-", "*", "/"] 
    root = Node(None, None, None, []) 
    expandBranch(root, nums, ops) 
    dfs(root, 154) 

if __name__ == "__main__": 
    main() 

出力を提供します：

[230, '+', 10, '/', 2, '+', 34] 
[67, '+', 10, '*', 2] 
[67, '*', 10, '/', 230, '*', 60, '+', 34] 
[67, '/', 230, '+', 60, '*', 2, '+', 34] 
[67, '/', 230, '+', 2, '*', 60, '+', 34] 
[34, '-', 67, '*', 2, '+', 230, '-', 10] 
[34, '-', 67, '*', 2, '-', 10, '+', 230] 
[34, '-', 2, '*', 67, '/', 10, '-', 60] 
[34, '/', 230, '+', 67, '+', 10, '*', 2] 
[34, '/', 230, '+', 10, '+', 67, '*', 2] 
[34, '/', 60, '+', 67, '+', 10, '*', 2] 
[34, '/', 60, '+', 10, '+', 67, '*', 2] 
[34, '/', 2, '+', 67, '+', 60, '+', 10] 
[34, '/', 2, '+', 67, '+', 10, '+', 60] 
[34, '/', 2, '+', 60, '+', 67, '+', 10] 
[34, '/', 2, '+', 60, '+', 10, '+', 67] 
[34, '/', 2, '+', 10, '+', 67, '+', 60] 
[34, '/', 2, '+', 10, '+', 60, '+', 67] 
[60, '*', 2, '+', 34] 
[60, '/', 230, '+', 67, '+', 10, '*', 2] 
[60, '/', 230, '+', 10, '+', 67, '*', 2] 
[60, '/', 34, '+', 230, '-', 67, '-', 10] 
[60, '/', 34, '+', 230, '-', 10, '-', 67] 
[60, '/', 34, '-', 67, '+', 230, '-', 10] 
[60, '/', 34, '-', 67, '-', 10, '+', 230] 
[60, '/', 34, '-', 10, '+', 230, '-', 67] 
[60, '/', 34, '-', 10, '-', 67, '+', 230] 
[60, '/', 34, '*', 67, '+', 10, '*', 2] 
[60, '/', 34, '*', 10, '+', 67, '*', 2] 
[2, '*', 60, '+', 34] 
[10, '+', 230, '/', 2, '+', 34] 
[10, '+', 67, '*', 2] 
[10, '*', 67, '/', 230, '*', 60, '+', 34] 
[10, '/', 230, '+', 60, '*', 2, '+', 34] 
[10, '/', 230, '+', 2, '*', 60, '+', 34] 
[10, '/', 67, '+', 60, '*', 2, '+', 34] 
[10, '/', 67, '+', 2, '*', 60, '+', 34] 

コードはかなり荒れていると、おそらく改善することができるここではPythonのコードです。整数の除算がコード内で発生することに注意してください。また、元のリストに数字を追加するほど、プログラムは指数関数的に遅くなります。