给定 4 个数字，使用基本运算符（+、-、*、/ 和括号）生成所有组合，结果为 24

Question

给定一个包含 4 个整数的列表，我必须使用基本数学运算符和括号找出它们的所有组合，使其计算结果为 24。例如，如果这 4 个数字是 1,2,3,4表达式 1*2*3*4 或 (4+2)*(3+1) 可以计算为 24。我找到算法 here 但我不完全理解它来实现程序。

简单的递归可以给出不包含括号的组合。我想了解如何解决涉及括号的问题。

Answer 1

如果我们没有括号，任务就很简单：我们所要做的就是枚举所有操作。假设我们有 +、-、*、/:

   1 + 2 + 3 + 4
   1 + 2 + 3 - 4
   1 + 2 + 3 * 4
   1 + 2 + 3 / 4
   1 + 2 - 3 + 4 
   1 + 2 - 3 - 4 
   1 + 2 - 3 * 4  
   1 + 2 - 3 / 4  
   1 + 2 * 3 + 4  
   ...
   1 / 2 / 3 + 4  
   1 / 2 / 3 - 4 
   1 / 2 / 3 * 4
   1 / 2 / 3 / 4

我们总共只有 4 ** 3 = 64 个公式。让我们添加括号。我们可以以 3! == 6 方式使用它们（让 ^ 成为 +, -, * 中的任何一个操作）：

   (((1 ^ 2) ^ 3) ^ 4)    // order of operations: 1, 2, 3
    ((1 ^ 2) ^ (3 ^ 4))   // -/-                  1, 3, 2 
    ((1 ^ (2 ^ 3)) ^ 4)   // -/-                  2, 1, 3 
     (1 ^ ((2 ^ 3) ^ 4))  // -/-                  2, 3, 1 
    ((1 ^ 2) ^ (3 ^ 4))   // -/-                  3, 1, 2 
     (1 ^ (2 ^ (3 ^ 4)))  // -/-                  3, 2, 1

现在我们有 64 * 6 == 384 个要测试的公式。

最后，我们可以洗牌（以 4! == 24 方式）：

  1 ^ 2 ^ 3 ^ 4
  1 ^ 2 ^ 4 ^ 3
  1 ^ 3 ^ 2 ^ 4 
  1 ^ 3 ^ 4 ^ 2  
  ...
  4 ^ 3 ^ 2 ^ 1

我们有 24 * 384 == 9216 个公式要执行，这可以通过蛮力完成（使用 eval 或等价物）

伪代码：

 # All possible arguments order
 for (permutationIndex in 0..23) {
   int[] numbers = Permutation({1, 2, 3, 4}, permutationIndex);  

   # All possible operations
   foreach (op1 in {"+", "-", "*", "/"})
     foreach (op2 in {"+", "-", "*", "/"}) 
       foreach (op3 in {"+", "-", "*", "/"}) {
         # All possible parenthesis 
         formulae[] = {
           "(((numbers[0] op1 numbers[1]) op2 numbers[2]) op3 numbers[3])",            
           "((numbers[0] op1 numbers[1]) op2 (numbers[2] op3 numbers[3]))",
           "((numbers[0] op1 (numbers[1] op2 numbers[2])) op3 numbers[3])", 
           "(numbers[0] op1 ((numbers[1] op2 numbers[2]) op3 numbers[3]))",
           "((numbers[0] op1 numbers[1]) op2 (numbers[2] op3 numbers[3]))", 
           "(numbers[0] op1 (numbers[1] op2 (numbers[2] op3 numbers[3])))",
         }

         foreach (formula in formulae)
           if (eval(formula) == 24)
             Write(formula); 
       }   
   }

Answer 2

要处理 'parenthesis-problem' 你可以这样想你的问题：

"Create all Binary Expression Trees containing the operators + - * / and the given numbers 1,2,3,4. The evaluated expression must be 24."

括号是树中隐式表示的求值顺序的结果。

所以简单地创建所有可能的树，评估它们以检查结果是否为 24，然后打印包括括号在内的有效树（通过在每个操作周围放置括号，或者仅在评估顺序需要它们时）

给定 4 个数字，使用基本运算符（+、-、*、/ 和括号）生成所有组合，结果为 24

Given 4 numbers generate all the combinations using basic operators (+, -, *,/ and parentheses)such that the result is 24

algorithm

binary-tree