求数组最小值的决策树生成算法及最小决策节点公式推导

我需要实现一个代码生成工具，输入参数为n（数组大小），生成包含两类节点的简易决策树程序：

• 决策节点：仅使用<、=、>三种运算符之一比较数组元素，不允许组合运算符或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()
)

print.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()
}

codegen.kt #

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!!
}

main.kt #

fun main() {
    val root = generateMinProgram(2)
    val code = generatePythonCode(root)
    println(code)
}

核心需求与咨询 #

我不需要修复现有代码，而是想了解：

1. 生成此类决策树的高层算法思路及对应的数据结构设计（回溯法是否适用？）
2. 我的核心目标是推导数组最小值查找所需的最小严格决策节点数公式，目前因为这个数学问题没有明确答案，才尝试通过代码生成的方式暴力推导。

内容的提问来源于stack exchange，提问作者sanitizedUser