我是 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。
我能够找到这篇文章，但它与我正在寻找的内容不太匹配，尤其是因为顺序对我来说并不重要 对集合中的项目求和以获得目标值的方法数 - 顺序很重要
因此，例如，我可以以这种方式手动执行每个组合：
if a + b + c + d == 24 {
print("a + b + c + d")
}
我的目标是让用户输入 4 个值，并让 IOS 生成所有可能的数学表达式的列表，结果为 24 个。
帕特里克
这里有一种方法。 从expressions数组和values数组开始。 最初，expressions只是values的String值：
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
前几条注释中引用的解决方案中未涵盖的一种简单方法是以反向波兰表示法(RPN( 生成候选表达式。如果您学习过CS，或者拥有HP计算器，您可能会记得这一点。RPN 的优点是它不包含括号，并且严格按照从左到右的顺序进行评估。点击链接查看完整说明，以下是几个示例：
代数： (a+b(*c
RPN： ab+c*
>代数： a+(b*c(RPN： abc*+
在大纲中，要从左到右计算 RPN 表达式，您将找到的任何变量推送到堆栈上。对于任何运算符，您弹出堆栈的 2 个值，将 与操作相结合，然后将结果推回堆栈。
要为您的问题生成单个表达式，大纲算法为：
while there are variables unused or fewer than (number of variables - 1) operators
either:
add any unused variable
or:
if the number of added variables is at least two greater than the
number of added operators add any operator
这将给你一个单一的表达式，生成所有这些思考递归。在每个阶段，您遍历上述所有选择，并为每个选项递归传递部分表达式、未使用的变量等。您可以将分部表达式存储在数组中，每个元素都是变量或运算符(想想enum(。由于 Swift 在递归时按值传递数组，因此每个调用都可以继续向数组添加元素，而不会影响其他调用。
在伪代码中：
generate(expression: array, variables: variable collection) -> collection
results <- empty collection
for nextVar in variables
add generate(expression + nextVar, variables - nextVar) to results
if #variables in expression - #operators in expression >= 2
for every possible operator
add generate(expression + operator, variables) to results
return results
生成完整表达式后，您可以对其进行计算，如果结果为 24，则可以将其添加到解决方案中。作为可能的优化，您可以在递归时进行评估，以节省部分表达式的重新计算。RPN 评估可以使用堆栈，您可以从 Swift 中的数组构建该堆栈，并在每次递归调用中传递。探索其他优化方法由您自行决定。
如果你在设计算法和编写一些代码后遇到困难，你可以问一个新问题 - 包括一个指向这个、你的算法、你的代码和你的问题的链接;毫无疑问，有人会帮助你。
呵呵