摘要

全排列生成器实现了生成给定数组的所有可能排列的功能。本文详细解析了输入解析、回溯法、交换法等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个不包含重复元素的整数数组，生成所有可能的排列。排列是指从数组中取出所有元素，按不同的顺序排列。

示例：

• 输入：nums = [1,2,3]
• 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• 共有 3! = 6 种排列

1.2 应用场景

• 密码破解
• 游戏设计
• 组合优化
• 算法竞赛

2. 核心算法原理

2.1 回溯法（推荐）

使用回溯算法，尝试每个位置的所有可能选择，使用标记数组避免重复选择。时间复杂度 O(n! × n)，空间复杂度 O(n)。

2.2 交换法

通过交换元素来生成排列，每次固定一个位置，然后递归处理剩余位置。时间复杂度 O(n! × n)，空间复杂度 O(1) 额外空间。

3. 代码实现详细解析

3.1 输入解析模块

var nums: List<Int>? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("nums=", ignoreCase = true) -> {
                val valuesStr = line.substringAfter("=").trim()
                try {
                    nums = valuesStr.split(",")
                        .map { it.trim() }
                        .filter { it.isNotEmpty() }
                        .map { it.toInt() }
                } catch (e: Exception) {
                    nums = null
                }
            }
            else -> {
                if (nums == null) {
                    try {
                        nums = line.split(",")
                            .map { it.trim() }
                            .filter { it.isNotEmpty() }
                            .map { it.toInt() }
                    } catch (e: Exception) {
                        nums = null
                    }
                }
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取整数数组。首先声明一个可空的整数列表 nums，初始值为 null。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，使用 when 表达式进行模式匹配。第一个分支处理 nums= 格式的输入：提取等号后面的部分作为数组字符串，然后使用 split(",") 按逗号分割，map { it.trim() } 去除空白字符，filter { it.isNotEmpty() } 过滤空元素，map { it.toInt() } 转换为整数。

使用 try-catch 块捕获可能的异常，确保程序的健壮性。如果解析失败，将 nums 设置为 null。

第二个分支处理没有前缀的情况：如果 nums 仍然为 null，则直接将当前行按逗号分割并转换为整数数组。这种设计提高了输入格式的灵活性，用户可以输入 nums=1,2,3 或直接输入 1,2,3。

3.2 回溯法实现（推荐）

fun permuteBacktrack(nums: List<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val used = BooleanArray(nums.size)

    fun backtrack(current: MutableList<Int>) {
        if (current.size == nums.size) {
            result.add(current.toList())
            return
        }

        for (i in nums.indices) {
            if (!used[i]) {
                used[i] = true
                current.add(nums[i])
                backtrack(current)
                current.removeAt(current.size - 1)
                used[i] = false
            }
        }
    }

    backtrack(mutableListOf())
    return result
}

代码解析：

这是回溯法的核心实现，通过递归和回溯来生成所有可能的排列。函数接受一个整数列表作为参数，返回所有排列的列表。

首先初始化数据结构：result 是一个可变列表，用于存储所有生成的排列。used 是一个布尔数组，大小为数组长度，用于标记哪些元素已经被使用过。

然后定义一个内部递归函数 backtrack，它接受一个可变列表 current，表示当前正在构建的排列。

在 backtrack 函数中，首先检查基本情况：如果 current.size == nums.size，说明当前排列已经包含了所有元素，是一个完整的排列。将当前排列（使用 toList() 创建副本）添加到结果列表中，然后返回。

如果当前排列还不完整，则尝试每个位置的所有可能选择。遍历数组的所有索引 i，如果元素 nums[i] 还没有被使用过（!used[i]），则：

1. 标记该元素为已使用（used[i] = true）
2. 将该元素添加到当前排列中（current.add(nums[i])）
3. 递归调用 backtrack，继续构建排列
4. 回溯：从当前排列中移除刚才添加的元素（current.removeAt(current.size - 1)）
5. 取消标记该元素为未使用（used[i] = false）

回溯是算法的关键部分。当递归返回后，需要撤销刚才的选择，这样下一次循环才能尝试其他可能的选择。通过这种方式，算法可以探索所有可能的排列。

例如，对于数组 [1,2,3]：

• 第一层递归：可以选择 1、2 或 3
• 如果选择了 1，进入第二层递归：可以选择 2 或 3
• 如果选择了 2，进入第三层递归：只能选择 3，得到一个完整排列 [1,2,3]
• 然后回溯，回到第二层，撤销选择 2，尝试选择 3，得到排列 [1,3,2]
• 继续回溯，回到第一层，撤销选择 1，尝试选择 2，以此类推

最后，从空列表开始调用 backtrack(mutableListOf())，然后返回所有生成的排列。

这个算法的时间复杂度是 O(n! × n)，其中 n 是数组的长度。因为有 n! 种排列，每种排列需要 O(n) 时间来构建。空间复杂度是 O(n)，因为递归调用的深度最多是 n，并且需要使用 used 数组和当前排列。

3.3 交换法实现

fun permuteSwap(nums: List<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val mutable = nums.toMutableList()

    fun swap(i: Int, j: Int) {
        val temp = mutable[i]
        mutable[i] = mutable[j]
        mutable[j] = temp
    }

    fun backtrack(start: Int) {
        if (start == mutable.size) {
            result.add(mutable.toList())
            return
        }

        for (i in start until mutable.size) {
            swap(start, i)
            backtrack(start + 1)
            swap(start, i) // 回溯
        }
    }

    backtrack(0)
    return result
}

代码解析：

这是交换法的实现，通过交换元素来生成排列，不需要额外的标记数组。函数接受一个整数列表作为参数，返回所有排列的列表。

首先初始化数据结构：result 是一个可变列表，用于存储所有生成的排列。mutable 是输入数组的可变副本。

然后定义一个辅助函数 swap，用于交换两个位置的元素。它接受两个索引 i 和 j，交换 mutable[i] 和 mutable[j]。

然后定义一个内部递归函数 backtrack，它接受一个参数 start，表示当前正在处理的位置。

在 backtrack 函数中，首先检查基本情况：如果 start == mutable.size，说明所有位置都已经处理完毕，当前数组状态就是一个完整的排列。将当前数组状态（使用 toList() 创建副本）添加到结果列表中，然后返回。

如果还有位置需要处理，则尝试将当前位置 start 与后续所有位置 i（从 start 到 mutable.size - 1）交换：

1. 交换位置 start 和 i 的元素（swap(start, i)）
2. 递归调用 backtrack(start + 1)，处理下一个位置
3. 回溯：再次交换位置 start 和 i 的元素（swap(start, i)），恢复原状

通过交换和回溯，算法可以生成所有可能的排列。每次交换都会固定当前位置，然后递归处理剩余位置。当递归返回后，通过再次交换来撤销选择，这样下一次循环才能尝试其他可能的选择。

例如，对于数组 [1,2,3]：

• start = 0：可以交换位置 0 和 0（不交换）、位置 0 和 1、位置 0 和 2
• 如果交换位置 0 和 0，数组保持 [1,2,3]，进入 backtrack(1)
• start = 1：可以交换位置 1 和 1、位置 1 和 2
• 如果交换位置 1 和 1，数组保持 [1,2,3]，进入 backtrack(2)
• start = 2：到达末尾，得到一个完整排列 [1,2,3]
• 然后回溯，继续尝试其他交换

这个算法的时间复杂度是 O(n! × n)，空间复杂度是 O(1) 额外空间（不考虑递归栈和输出空间），因为不需要额外的标记数组，只需要交换元素。

3.4 阶乘函数

fun factorial(n: Int): Int {
    return if (n <= 1) 1 else (1..n).reduce { acc, i -> acc * i }
}

代码解析：

这个函数计算阶乘，用于验证排列数量的正确性。函数接受一个整数 n 作为参数，返回 n!。

首先处理基本情况：如果 n <= 1，返回 1（0! = 1, 1! = 1）。

否则，使用 (1..n).reduce { acc, i -> acc * i } 计算阶乘。(1..n) 创建一个从 1 到 n 的整数范围，reduce 函数将这个范围内的所有数字相乘。

例如，对于 n = 3：

• 范围是 [1, 2, 3]
• reduce 操作：1 * 2 * 3 = 6
• 所以 factorial(3) = 6

这个函数用于验证生成的排列数量是否正确。对于长度为 n 的数组，如果没有重复元素，应该有 n! 种排列。

4. 算法复杂度分析

4.1 时间复杂度

• 回溯法：O(n! × n)，有 n! 种排列，每种排列需要 O(n) 时间构建
• 交换法：O(n! × n)，有 n! 种排列，每种排列需要 O(n) 时间构建
• 总体时间复杂度：O(n! × n)

4.2 空间复杂度

• 回溯法：O(n)，递归深度最多为 n，需要使用标记数组
• 交换法：O(1) 额外空间，不需要额外的标记数组
• 输出空间：O(n! × n)，需要存储所有排列

5. 算法优化建议

5.1 剪枝优化

对于包含重复元素的数组，可以使用剪枝技术跳过重复的排列。

5.2 边界条件处理

代码已经处理了各种边界情况：空数组、单个元素等情况。

5.3 性能优化

两种方法的时间复杂度相同，回溯法思路更清晰，推荐使用。

6. 应用场景扩展

1. 密码破解：生成所有可能的密码组合
2. 游戏设计：生成游戏中的排列组合
3. 组合优化：解决组合优化问题
4. 算法竞赛：LeetCode 等平台的经典问题
5. 扩展问题：带重复元素的全排列、部分排列、组合等变体

7. 总结

全排列生成器实现了两种生成方法，核心要点：

1. 回溯法：推荐，思路清晰，使用标记数组避免重复选择
2. 交换法：通过交换元素生成排列，不需要额外的标记数组
3. 回溯机制：关键是在递归返回后撤销选择，尝试其他可能
4. 时间复杂度：两种方法都是 O(n! × n)，排列数量随数组长度快速增长

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如密码破解、游戏设计、组合优化等场景。回溯法的思想也可以应用到其他类似的搜索和生成问题中。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net