값 목록 및 수학 연산에 대한 수학 식 찾기 (또는 무차별 대입)

Question

그래서 몇 가지 값이 포함 된 목록이 있습니다. [230, 67, 34, 60, 2, 10]
그리고 미리 알고있는 작업 목록 [operations.add, operations.sub, operations.mul, operations.div]과 result number입니다.

내게 결과를 줄 수있는 가능한 모든 수학적 표현식을 찾는 가장 좋은 방법은 무엇입니까?

예를 들어 결과가 154 인 경우 가능한 해결책은 60*2+34입니다.

이 알고리즘을 설계 할 때의 문제점은 표현식에 어떤 값과 연산이 사용되는지 미리 알 수 없기 때문이며, 그렇지 않은 경우 또는 모두 사용됩니다.
파이썬 코드를 제공 할 수 있다면 감사하겠습니다.
미리 감사드립니다.

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] 

코드는 매우 거친이며 아마 향상시킬 수 여기 파이썬 코드입니다. 정수 부분이 코드에서 발생합니다. 또한 원래 목록에 더 많은 숫자를 추가하면 프로그램이 기하 급수적으로 느려질 것입니다.