java 递归排列

admin 2026年02月27日 06:02 102 0

Java递归排列是利用递归思想生成全列的核心方法，其核心逻辑为“固定+递归+组合”：通过固定当前位置元素，对剩余元素递归排列，直至剩余元素为空时将当前排列加入结果集，对字符串"abc"，先固定'a'，递归排列"bc"得"bc""cb"，组合成"abc""acb"；再固定'b'，递归排列"ac"得"ac""ca"，组合成"bac""bca"，依此类推，实现时需注意递归终止条件（起始索引等于数组长度）及元素交换逻辑，避免重复排列，该方法代码简洁，但需注意递归深度可能导致的栈溢出风险，适用于小规模数据排列。

Java递归排列：从原理到实践，轻松掌握全排列算法

什么是排列？为什么用递归实现？

排列是数学中的基础概念，指从一组元素中按特定顺序选取全部或部分元素进行组合的方式。全排列特指给定一组不重复元素时，输出所有可能的顺序组合，例如数组 `[1, 2, 3]` 的全排列共有 `3! = 6` 种，具体为：`[1,2,3]`、`[1,3,2]`、`[2,1,3]`、`[2,3,1]`、`[3,1,2]`、`[3,2,1]`。

递归是一种通过函数自我调用解决问题的编程范式,其核心在于分治思想与回溯机制：将复杂问题分解为更小的子问题，递归解决子问题后撤销操作（回溯），继续探索其他可能性，排列问题天然契合递归特性——固定一个元素，递归排列剩余元素，因此递归实现既直观又高效。

递归排列的核心思想：固定+递归+回溯

假设要对数组 `nums` 进行全排列，递归排列的核心步骤可拆解为三步： 1. **固定当前元素**：从当前位置开始，依次选择每个元素作为当前排列的固定点 2. **递归排列剩余元素**：固定当前元素后，对剩余未固定元素进行递归处理 3. **回溯撤销选择**：递归返回后，恢复数组原始状态，尝试下一个元素

这一过程可通过交换法实现：每次将当前位置元素与后续元素交换，固定交换后的元素，递归处理下一位置；递归结束后交换恢复（回溯），确保后续操作不受影响。

Java实现递归全排列

基础实现（无重复元素）

以下是对无重复数组进行全排列的Java实现，采用递归+交换法： ```java import java.util.ArrayList; import java.util.List;

public class RecursivePermutation { public static List<List> permute(int[] nums) { List<List> result = new ArrayList<>(); backtrack(nums, 0, result); return result; }

private static void backtrack(int[] nums, int start, List<List<Integer>> result) {
    // 终止条件：所有元素已固定
    if (start == nums.length) {
        List<Integer> permutation = new ArrayList<>();
        for (int num : nums) {
            permutation.add(num);
        }
        result.add(permutation);
        return;
    }
    // 从start位置开始，依次交换每个元素到当前位置
    for (int i = start; i < nums.length; i++) {
        // 交换元素，固定nums[i]到当前位置
        swap(nums, start, i);
        // 递归处理剩余元素
        backtrack(nums, start + 1, result);
        // 回溯：恢复数组状态
        swap(nums, start, i);
    }
}
private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
public static void main(String[] args) {
    int[] nums = {1, 2, 3};
    List<List<Integer>> permutations = permute(nums);
    System.out.println("全排列结果：" + permutations);
    // 输出：全排列结果：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}


<h4>代码解析</h4>
- **`permute` 方法**：初始化结果列表，启动递归排列
- **`backtrack` 方法**：递归核心逻辑
  - **终止条件**：当 `start` 指针到达数组末尾时，表示当前排列完成
  - **递归过程**：
    1. 交换 `start` 和 `i` 位置元素，固定 `nums[i]`
    2. 递归处理 `start+1` 位置后的剩余元素
    3. 回溯恢复交换前的状态
- **`swap` 方法**：辅助函数，实现数组元素交换
**时间复杂度**：O(n!) - n个元素的全排列数量  
**空间复杂度**：O(n) - 递归调用栈深度
<h3>递归排列的扩展：处理重复元素</h3>
当数组包含重复元素时，直接使用交换法会产生重复排列（如 `[1,1,2]` 会生成重复结果），解决方案是在递归过程中**跳过重复元素**，避免重复固定。
<h4>优化后的代码（处理重复元素）</h4>
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PermutationWithDuplicates {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 排序使重复元素相邻
        backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
        return result;
    }
    private static void backtrack(int[] nums, boolean[] used, 
                               List<Integer> path, List<List<Integer>> result) {
        // 终止条件：路径长度等于数组长度
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 跳过已使用的元素
            if (used[i]) continue;
            // 跳过重复元素：若当前元素与前一个相同且前一个未使用
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            // 选择当前元素
            used[i] = true;
            path.add(nums[i]);
            // 递归处理剩余元素
            backtrack(nums, used, path, result);
            // 回溯：撤销选择
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        List<List<Integer>> permutations = permuteUnique(nums);
        System.out.println("去重全排列结果：" + permutations);
        // 输出：去重全排列结果：[[1,1,

标签： #排列算法