swift - 导出集合中所有可能的数学表达式以获得目标值的算法

Question

我是 Swift 编程的新手，虽然我可以想出这个应用程序的其余部分，但我脑子里浮现的是，我很难弄清楚如何推导出可以处理这个问题的算法:

给定一组 4 个值(可能最好使用 Double，因为有些甚至可以是分数)，导出返回目标值结果的所有可能组合——在我的例子中是 24。

例如，a+b+c+d、a+b+d+c、a+d+b+c、d+a+b+c，以及该集合的所有排列，加上所有可能的数学运算符例如 (a*b)^(c-d) 或 (a+b+c)/d。

我能够找到这篇文章，但它与我正在寻找的内容不太相符，尤其是顺序对我来说并不重要 Number of ways to sum the items in a set to get a target value - Order matters

例如，我可以通过这种方式手动完成每个组合:

if a + b + c + d == 24 {
  print("\a + \b + \c + \d")
}

我的目标是让用户输入 4 个值，然后让 IOS 生成一个列表，其中包含所有可能得出 24 的数学表达式。

帕特里克

Answer 1

这是一种方法。从 expressions 的数组开始和一组 values .最初，expressions只是 String values 的值(value):

let expressions = ["1", "2", "3", "4"]
let values = [1, 2, 3, 4]

选择两个表达式(例如“1”和“2”，以及一个二元运算符 (“+”)，并将它们组合起来创建具有 3 个值的 expressions 和 values:

expressions = ["3", "4", "(1 + 2)"]
values = [3, 4, 3]

重复此过程，再次将两个表达式与一个操作组合起来:

expressions = ["3", "(4 + (1 + 2))"]
values = [3, 7]

最后，将最后两个表达式用“+”组合起来:

expressions = ["(3 + (4 + (1 + 2)))"]
values = [10]

到达单个表达式后，检查该值是否与您的目标匹配。

---

以下是一个递归函数，它尝试所有值和操作的组合来创建表达式以搜索目标:

import Foundation

// An array of tuples containing an operator name and a closure 
// that performs the operation
let ops: [(name: String, function: (Double, Double) -> Double)] = [
    ("+", { $0 + $1 }),
    ("-", { $0 - $1 }),
    ("*", { $0 * $1 }),
    ("/", { $0 / $1 }),
    ("^", { pow($0, $1) })
]


func compute(expressions: [String], values: [Double], target: Double) {
    
    // base case of the recursion: if there is only one
    // expression and one value, check if the value is the
    // target value we're looking for and print the expression
    // and value if the target is matched
    if expressions.count == 1 {
        if values[0] == target {
            print("\(expressions[0]) = \(values[0])")
        }
    } else if expressions.count >= 2 {

        // loop through all of the expressions choosing each
        // as the first expression
        for idx1 in expressions.indices {

            // copy the expressions and values arrays so that
            // we can remove the expression and value
            // without modifying the original arrays
            // which will be needed for the next try
            var expcopy = expressions
            var valcopy = values
            let exp1 = expcopy.remove(at: idx1)
            let val1 = valcopy.remove(at: idx1)
            
            // loop through the remaining expressions to find
            // the second one
            for idx2 in expcopy.indices {
                // again, copy the arrays to keep from modifying
                // the originals while searching
                var expcopy2 = expcopy
                var valcopy2 = valcopy
                
                let exp2 = expcopy2.remove(at: idx2)
                let val2 = valcopy2.remove(at: idx2)

                // now try all possible operations to combine
                // the two expressions
                for op in ops {
                    // use the closure to compute the value
                    let value = op.function(val1, val2)

                    // combine the expressions into a new string
                    // expression with the operator in the
                    // middle and surrounded by () if this is
                    // not the top level expression
                    var exp = "\(exp1) \(op.name) \(exp2)"
                    if !expcopy2.isEmpty {
                        exp = "(\(exp))"
                    }

                    // now that we've reduced the number of
                    // expressions by 1, recurse by calling
                    // compute again on the reduced list of
                    // expressions
                    compute(expressions: expcopy2 + [exp], values: valcopy2 + [value], target: target)
                }
            }
        }
    }
}


// This helper function creates the array of expressions from
// the array of values, and then calls the main function above
// to do the real work  
func search(values: [Double], target: Double) {
    compute(expressions: values.map { String($0) }, values: values, target: target)
}

---

示例 1:

search(values: [1, 2, 3, 4], target: 121)

输出:

(1.0 - (3.0 * 4.0)) ^ 2.0 = 121.0
((3.0 * 4.0) - 1.0) ^ 2.0 = 121.0
(1.0 - (4.0 * 3.0)) ^ 2.0 = 121.0
((4.0 * 3.0) - 1.0) ^ 2.0 = 121.0

---

示例 2:

search(values: [1, 2, 3], target: 1)

输出:

3.0 / (1.0 + 2.0) = 1.0
(1.0 + 2.0) / 3.0 = 1.0
3.0 - (1.0 * 2.0) = 1.0
(1.0 ^ 2.0) ^ 3.0 = 1.0
(1.0 * 3.0) - 2.0 = 1.0
2.0 - (1.0 ^ 3.0) = 1.0
(1.0 ^ 3.0) ^ 2.0 = 1.0
3.0 / (2.0 + 1.0) = 1.0
(2.0 + 1.0) / 3.0 = 1.0
(2.0 - 1.0) ^ 3.0 = 1.0
3.0 - (2.0 * 1.0) = 1.0
3.0 - (2.0 / 1.0) = 1.0
3.0 - (2.0 ^ 1.0) = 1.0
1.0 ^ (2.0 + 3.0) = 1.0
1.0 ^ (2.0 - 3.0) = 1.0
1.0 ^ (2.0 * 3.0) = 1.0
1.0 ^ (2.0 / 3.0) = 1.0
1.0 ^ (2.0 ^ 3.0) = 1.0
2.0 / (3.0 - 1.0) = 1.0
(3.0 - 1.0) / 2.0 = 1.0
(3.0 * 1.0) - 2.0 = 1.0
(3.0 / 1.0) - 2.0 = 1.0
(3.0 ^ 1.0) - 2.0 = 1.0
1.0 ^ (3.0 + 2.0) = 1.0
1.0 * (3.0 - 2.0) = 1.0
1.0 / (3.0 - 2.0) = 1.0
1.0 ^ (3.0 - 2.0) = 1.0
(3.0 - 2.0) * 1.0 = 1.0
(3.0 - 2.0) / 1.0 = 1.0
(3.0 - 2.0) ^ 1.0 = 1.0
1.0 ^ (3.0 * 2.0) = 1.0
1.0 ^ (3.0 / 2.0) = 1.0
1.0 ^ (3.0 ^ 2.0) = 1.0

---

消除重复的解决方案

如果有 4 个或更多值，或者甚至更少的值不是唯一的，您最终可能会得到重复的表达式。消除重复项的方法是使用 Set<String>跟踪您已经找到的表达式并检查是否设置了 contains您的新表达式，然后将其打印为新解决方案。

import Foundation

// An array of tuples containing an operator name and a closure
// that performs the operation
let ops: [(name: String, function: (Double, Double) -> Double)] = [
    ("+", { $0 + $1 }),
    ("-", { $0 - $1 }),
    ("*", { $0 * $1 }),
    ("/", { $0 / $1 }),
    ("^", { pow($0, $1) })
]


func compute(expressions: [String], values: [Double], target: Double, solutions: inout Set<String>) {
    
    // base case of the recursion: if there is only one
    // expression and one value, check if the value is the
    // target value we're looking for and print the expression
    // and value if the target is matched and we don't already
    // have that expression in our set of solutions
    if expressions.count == 1 {
        if values[0] == target && !solutions.contains(expressions[0]) {
            print("\(expressions[0]) = \(values[0])")
            solutions.insert(expressions[0])
        }
    } else if expressions.count >= 2 {
        
        // loop through all of the expressions choosing each
        // as the first expression
        for idx1 in expressions.indices {
            
            // copy the expressions and values arrays so that
            // we can remove the expression and value
            // without modifying the original arrays
            // which will be needed for the next try
            var expcopy = expressions
            var valcopy = values
            
            let exp1 = expcopy.remove(at: idx1)
            let val1 = valcopy.remove(at: idx1)
            
            // loop through the remaining expressions to find
            // the second one
            for idx2 in expcopy.indices {
                // again, copy the arrays to keep from modifying
                // the originals while searching
                var expcopy2 = expcopy
                var valcopy2 = valcopy
                
                let exp2 = expcopy2.remove(at: idx2)
                let val2 = valcopy2.remove(at: idx2)
                
                // now try all possible operations to combine
                // the two expressions
                for op in ops {
                    // use the op's function to compute the value
                    let val = op.function(val1, val2)
                    
                    // combine the expressions into a new string
                    // expression with the operator in the
                    // middle and surrounded by () if this is
                    // not the top level expression
                    var exp = "\(exp1) \(op.name) \(exp2)"
                    if !expcopy2.isEmpty {
                        exp = "(\(exp))"
                    }
                    
                    // now that we've reduced the number of
                    // expressions by 1, recurse by calling
                    // compute again on the reduced list of
                    // expressions
                    let newexp = expcopy2 + [exp]
                    let newval = valcopy2 + [val]
                    compute(expressions: newexp, values: newval, target: target, solutions: &solutions)
                }
            }
        }
    }
}


// This helper function creates the array of expressions from
// the array of values, creates a Set to hold the solutions, and
// then calls the main function above to do the real work
func search(values: [Double], target: Double) {
    // create a set to keep track of solutions found so far
    var solutions = Set<String>()
    
    compute(expressions: values.map { String($0) }, values: values, target: target, solutions: &solutions)
    
    print("\n\(solutions.count) unique solutions were found")
}

---

示例:

search(values: [2, 2, 1], target: 5)

输出:

1.0 + (2.0 + 2.0) = 5.0
(2.0 + 2.0) + 1.0 = 5.0
1.0 + (2.0 * 2.0) = 5.0
(2.0 * 2.0) + 1.0 = 5.0
1.0 + (2.0 ^ 2.0) = 5.0
(2.0 ^ 2.0) + 1.0 = 5.0
2.0 + (2.0 + 1.0) = 5.0
(2.0 + 1.0) + 2.0 = 5.0
2.0 + (1.0 + 2.0) = 5.0
(1.0 + 2.0) + 2.0 = 5.0

10 unique solutions were found