Go语言实现排列组合的非递归算法（从零开始掌握非递归排列组合）

什么是排列与组合？

• 排列（Permutation）：从 n 个不同元素中取出 m 个元素，按照一定顺序排成一列。例如 [1,2,3] 的全排列有 6 种：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。
• 组合（Combination）：从 n 个不同元素中取出 m 个元素，不考虑顺序。例如 [1,2,3] 中取 2 个的组合有 3 种：[1,2], [1,3], [2,3]。

为什么使用非递归实现？

递归虽然代码简洁，但在处理大数据量时容易导致栈溢出。而非递归方法通过循环和辅助数据结构（如栈或数组）模拟递归过程，具有更好的内存控制能力，是工业级应用的首选。

Go语言实现排列的非递归算法

我们使用“字典序法”来生成全排列。其核心思想是：从当前排列出发，找到下一个字典序更大的排列，直到无法再生成为止。

// permuteNonRecursive 生成 slice 的所有排列（非递归）func permuteNonRecursive(nums []int) [][]int {    // 先排序，确保从最小字典序开始    sort.Ints(nums)    result := [][]int{}        for {        // 保存当前排列        current := make([]int, len(nums))        copy(current, nums)        result = append(result, current)                // 找到下一个排列        if !nextPermutation(nums) {            break        }    }    return result}// nextPermutation 修改 nums 为下一个字典序排列，若已是最大则返回 falsefunc nextPermutation(nums []int) bool {    n := len(nums)    i := n - 2        // 从右往左找第一个 nums[i] < nums[i+1]    for i >= 0 && nums[i] >= nums[i+1] {        i--    }        if i < 0 {        return false // 已是最大排列    }        // 从右往左找第一个大于 nums[i] 的元素    j := n - 1    for nums[j] <= nums[i] {        j--    }        // 交换 nums[i] 和 nums[j]    nums[i], nums[j] = nums[j], nums[i]        // 反转 i+1 到末尾    reverse(nums[i+1:])    return true}// reverse 反转切片func reverse(arr []int) {    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {        arr[i], arr[j] = arr[j], arr[i]    }}

Go语言实现组合的非递归算法

组合可以用“位掩码”或“索引递增法”实现。这里我们采用后者：维护一个长度为 k 的索引数组，每次尝试将最右边可递增的索引加 1，并重置其右侧索引。

// combineNonRecursive 从 nums 中选出 k 个元素的所有组合（非递归）func combineNonRecursive(nums []int, k int) [][]int {    if k <= 0 || k > len(nums) {        return [][]int{}    }        n := len(nums)    result := [][]int{}        // 初始化索引：[0, 1, 2, ..., k-1]    indices := make([]int, k)    for i := 0; i < k; i++ {        indices[i] = i    }        for {        // 构建当前组合        combo := make([]int, k)        for i, idx := range indices {            combo[i] = nums[idx]        }        result = append(result, combo)                // 寻找可递增的位置        i := k - 1        for i >= 0 && indices[i] == n - k + i {            i--        }                if i < 0 {            break // 所有组合已生成        }                // 递增该位置，并重置右侧        indices[i]++        for j := i + 1; j < k; j++ {            indices[j] = indices[j-1] + 1        }    }        return result}

完整示例与测试

下面是一个完整的 Go 程序，演示如何使用上述函数：

package mainimport (    "fmt"    "sort")// 此处省略 permuteNonRecursive、nextPermutation、reverse、combineNonRecursive 的定义func main() {    nums := []int{1, 2, 3}        fmt.Println("全排列（非递归）:")    perms := permuteNonRecursive(nums)    for _, p := range perms {        fmt.Println(p)    }        fmt.Println("\n组合 C(3,2)（非递归）:")    combos := combineNonRecursive(nums, 2)    for _, c := range combos {        fmt.Println(c)    }}

运行结果：

全排列（非递归）:[1 2 3][1 3 2][2 1 3][2 3 1][3 1 2][3 2 1]组合 C(3,2)（非递归）:[1 2][1 3][2 3]

总结

通过本文，你已经学会了如何用Go语言实现排列组合的非递归算法。这些方法不仅避免了递归的性能隐患，还提升了代码的健壮性。无论你是准备面试，还是开发高性能系统，掌握这些技巧都大有裨益。

记住我们的核心关键词：Go语言排列组合、非递归算法、Go实现排列组合、算法教程。多加练习，你也能写出优雅高效的算法代码！