新的代码生成工具仅接受一个输入 -n即输入数组的大小。然后，该工具应生成一个包含两种节点的简单决策树程序：
- 严格比较的决策节点
- 输出节点（叶）
决策节点使用 3 个运算符中的 1 个来比较输入数组中的两个元素 - <, =, >。不允许使用这些运算符的组合。也不允许使用额外的布尔运算符，例如 NOT、AND、OR。
输出节点指定从输入数组返回哪些元素。这些元素应全部具有相同的值，并且该值是整个输入数组的最小值。
到目前为止，我尝试使用基于堆栈的方法，该方法为长度为 2 的输入数组生成正确的代码，但对于每个更大的长度都会失败。输出如下所示：
if input[0] < input[1]:
return input[0]
else:
if input[0] == input[1]:
return input[0, 1]
else:
return input[1]
这是我的代码：
Node.kt
import ComparisonOperator.*
enum class ComparisonOperator {
LESS_THAN, EQUALS, GREATER_THAN
}
class Node (
val trueBranch: Node? = null,
val falseBranch: Node? = null,
val operator: ComparisonOperator = LESS_THAN,
val indices: IntArray = intArrayOf()
)
打印.kt
import TaskType.*
enum class TaskType {
PROCESS_NODE,
PROCESS_ELSE
}
data class StackEntry(val node: Node, val indent: Int, val taskType: TaskType)
fun generatePythonCode(root: Node): String {
val builder = StringBuilder()
val stack = ArrayDeque<StackEntry>()
stack.addLast(StackEntry(root, 0, PROCESS_NODE))
while (stack.isNotEmpty()) {
val entry = stack.removeLast()
val node = entry.node
val indent = entry.indent
val indentStr = " ".repeat(indent)
when (entry.taskType) {
PROCESS_NODE -> {
if (node.trueBranch == null) {
// Leaf node: output the return statement.
val indices = node.indices.joinToString(", ")
builder.append(indentStr).append("return input[").append(indices).append("]\n")
} else {
// Decision node: output an if statement.
val left = "input[${node.indices[0]}]"
val right = "input[${node.indices[1]}]"
val op = when (node.operator) {
ComparisonOperator.LESS_THAN -> "<"
ComparisonOperator.EQUALS -> "=="
ComparisonOperator.GREATER_THAN -> ">"
}
builder.append(indentStr).append("if ").append(left).append(" $op ").append(right).append(":\n")
// Push the false branch as an else task (it will add the "else:" line).
stack.addLast(StackEntry(node.falseBranch!!, indent, PROCESS_ELSE))
// Then push the true branch for processing with increased indent.
stack.addLast(StackEntry(node.trueBranch, indent + 1, PROCESS_NODE))
}
}
PROCESS_ELSE -> {
// For an else task, output the "else:" line and then process the node.
builder.append(indentStr).append("else:\n")
stack.addLast(StackEntry(node, indent + 1, PROCESS_NODE))
}
}
}
return builder.toString().trimEnd()
}
代码生成
import ComparisonOperator.*
enum class FrameType {
EQUALITY,
MERGE
}
// Each frame holds the current candidate groups (each a List<Int>).
// When the number of candidate groups is 1, a leaf (output) node is produced.
// Otherwise, two candidate groups are extracted and processed.
data class Frame(
val candidates: List<List<Int>>,
val type: FrameType,
var step: Int = 0,
var group1: List<Int>? = null,
var group2: List<Int>? = null,
var rest: List<List<Int>> = emptyList(),
// For a MERGE frame, we need:
// branchTrue: result for candidate list [group1] + rest.
// branchEquality (i.e. the nested equality decision) will be built from two subbranches.
// For an EQUALITY frame, we only need branchTrue and branchFalse.
var branchTrue: Node? = null,
var branchFalse: Node? = null,
// Temporary field to hold a generated child result.
var tempResult: Node? = null
)
// The function generateMinProgram builds the decision tree (as Node objects) that, when interpreted,
// returns the indices of all occurrences of the minimum element from the input array.
// It uses a brute-force backtracking strategy based on a stack.
fun generateMinProgram(n: Int): Node {
// Assume n >= 2. Initially, each candidate group is a single index.
val initialCandidates = (0 until n).map { listOf(it) }
val stack = ArrayDeque<Frame>()
// The outermost decision is always a MERGE.
stack.add(Frame(candidates = initialCandidates, type = FrameType.MERGE))
// The iterative DFS: process the frames until the root decision is built.
var result: Node? = null
while (stack.isNotEmpty()) {
val current = stack.last()
// If the candidate list has only one candidate group, create a leaf (output) node.
if (current.candidates.size == 1) {
// This candidate group represents the indices that are equal to the minimum.
result = Node(
trueBranch = null,
falseBranch = null,
// For output nodes the operator value is not used.
operator = LESS_THAN,
indices = current.candidates.first().toIntArray()
)
stack.removeLast()
if (stack.isNotEmpty()) {
// Propagate the result to the parent frame.
stack.last().tempResult = result
} else {
// No parent exists; this would happen if n==1 (but we assume n>=2).
return result
}
continue
}
// Otherwise, there is at least a decision to be made.
when (current.type) {
FrameType.MERGE -> {
// MERGE frame has three main phases.
when (current.step) {
0 -> {
// Initialize: pick the first two candidate groups.
current.group1 = current.candidates[0]
current.group2 = current.candidates[1]
current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
// Process the "true" branch for the primary decision:
// if input[group1[0]] < input[group2[0]] then the winner is group1.
val trueCandidates = listOf(current.group1!!) + current.rest
// New frame for processing the "true" branch.
stack.add(Frame(candidates = trueCandidates, type = FrameType.MERGE))
current.step = 1
}
1 -> {
// Coming back from the "true" branch.
current.branchTrue = current.tempResult
current.tempResult = null
// Next, process the nested equality decision.
// Create a new EQUALITY frame.
// For equality: if input[group1[0]] == input[group2[0]], then we merge group1 and group2.
// The candidate list becomes [group1 U group2] + rest.
val merged = current.group1!! + current.group2!!
val eqCandidates = listOf(merged) + current.rest
stack.add(Frame(candidates = eqCandidates, type = FrameType.EQUALITY))
current.step = 2
}
2 -> {
// Returning from the equality branch's "true" part (for the equality decision).
// In a MERGE frame, we now go to process the "false" branch of the nested equality:
current.branchTrue = current.branchTrue // holds nothing new; we now reuse the equality structure.
// For the "false" branch of the equality decision (i.e. when input[group1[0]] is not equal to input[group2[0]])
// we take group2 as the winner. Candidate list becomes [group2] + rest.
val falseCandidates = listOf(current.group2!!) + current.rest
stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
current.step = 3
}
3 -> {
// Coming back from the equality frame "false" branch.
current.branchFalse = current.tempResult
current.tempResult = null
// Build the nested equality decision node.
// This node has operator EQUALS and compares the same indices from group1 and group2.
val eqNode = Node(
trueBranch = current.tempResult ?: run {
// The true branch result is already stored in branch from the equality frame "true",
// which was set when processing the equality frame. In this MERGE frame, we expect the equality
// decision to have been constructed by processing the two equality branches.
// Here we use current.branchTrue that was computed in step 2.
current.branchTrue
},
falseBranch = current.branchFalse,
operator = EQUALS,
indices = intArrayOf(current.group1!![0], current.group2!![0])
)
// Build the primary decision node.
val mergeNode = Node(
trueBranch = current.branchTrue,
falseBranch = eqNode,
operator = LESS_THAN,
indices = intArrayOf(current.group1!![0], current.group2!![0])
)
stack.removeLast() // Done with current MERGE frame.
if (stack.isNotEmpty()) {
stack.last().tempResult = mergeNode
} else {
return mergeNode
}
}
}
}
FrameType.EQUALITY -> {
// EQUALITY frame has two phases.
when (current.step) {
0 -> {
// In an EQUALITY frame the comparison is always on the two groups that formed the candidate list.
// Since we always pass a candidate list with at least one candidate, if there are at least two,
// then we perform a decision test.
current.group1 = current.candidates[0]
current.group2 = current.candidates[0] // In an equality frame candidate list is built from either merged groups or single group2.
// For an EQUALITY frame, if there is more than one candidate group then we consider the first two.
// However, in our usages we've built the candidate list so that its size should be 1.
// To support a generic approach we check:
if (current.candidates.size >= 2) {
current.group2 = current.candidates[1]
current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
} else {
// If candidate list size is 1, then we are at a leaf even in an equality frame.
val leaf = Node(
trueBranch = null,
falseBranch = null,
operator = EQUALS,
indices = current.candidates.first().toIntArray()
)
stack.removeLast()
if (stack.isNotEmpty()) {
stack.last().tempResult = leaf
} else {
return leaf
}
continue
}
// Process the "true" branch of the equality decision:
// If input[group1[0]] == input[group2[0]], then the result candidate list remains as-is.
// (In our usage, for the equality branch, candidate list is already merged.)
val trueCandidates = current.candidates
stack.add(Frame(candidates = trueCandidates, type = FrameType.EQUALITY))
current.step = 1
}
1 -> {
// Return from the "true" branch.
current.branchTrue = current.tempResult
current.tempResult = null
// Process the "false" branch:
// In our usage, the "false" branch for an EQUALITY decision comes from a candidate list built for group2.
// We expect that candidate list to have a single candidate group.
val falseCandidates = if (current.candidates.size >= 2) {
// Use the second candidate alone alongside any remaining candidates.
listOf(current.candidates[1]) + current.rest
} else {
current.candidates
}
stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
current.step = 2
}
2 -> {
// Return from the "false" branch.
current.branchFalse = current.tempResult
current.tempResult = null
// Build the equality decision node.
val eqNode = Node(
trueBranch = current.branchTrue,
falseBranch = current.branchFalse,
operator = EQUALS,
indices = intArrayOf(current.candidates[0][0], if (current.candidates.size >= 2) current.candidates[1][0] else current.candidates[0][0])
)
stack.removeLast()
if (stack.isNotEmpty()) {
stack.last().tempResult = eqNode
} else {
return eqNode
}
}
}
}
}
}
// Should never reach here.
return result!!
}
主页.kt
fun main() {
val root = generateMinProgram(2)
val code = generatePythonCode(root)
println(code)
}
我不会要求你修复我的代码。相反，我正在寻找一种高级算法及其数据结构的描述。也许回溯解决方案就足够了？
这也是一个 XY 问题，因为我真正需要的是对这个问题的答案：我们如何推导出数组“最小值查找”中最小严格决策节点的公式？该问题的浏览量不多，因此我尝试通过强制执行代码生成步骤来找出公式。