Java排列生成详解（从零开始掌握全排列算法与递归实现）

使用递归实现排列生成

在 Java排列生成 中，最常用的方法是递归实现排列。其核心思想是：固定一个位置，然后对剩下的元素进行全排列。

步骤解析：

1. 从第一个位置开始，尝试放入每一个未使用的数字；
2. 标记该数字为“已使用”；
3. 递归处理下一个位置；
4. 回溯：取消标记，尝试下一个数字。

完整代码示例：

import java.util.*;public class PermutationGenerator {    public static void main(String[] args) {        int[] nums = {1, 2, 3};        List<List<Integer>> result = new ArrayList<>();        boolean[] used = new boolean[nums.length];        backtrack(nums, new ArrayList<>(), used, result);        // 打印所有排列        for (List<Integer> perm : result) {            System.out.println(perm);        }    }    // 回溯函数：生成全排列    private static void backtrack(            int[] nums,            List<Integer> current,            boolean[] used,            List<List<Integer>> result) {        // 递归终止条件：当前排列长度等于原数组长度        if (current.size() == nums.length) {            result.add(new ArrayList<>(current));            return;        }        for (int i = 0; i < nums.length; i++) {            if (!used[i]) {                // 选择                current.add(nums[i]);                used[i] = true;                // 递归                backtrack(nums, current, used, result);                // 回溯（撤销选择）                current.remove(current.size() - 1);                used[i] = false;            }        }    }}

代码说明

- used[] 数组用于记录哪些数字已经被使用；
- current 列表保存当前正在构建的排列；
- 当 current.size() 等于原数组长度时，说明找到一个完整排列，将其加入结果集；
- 每次递归返回后，必须执行“回溯”操作，即移除刚加入的元素并重置使用状态，以便尝试其他可能性。

运行结果

运行上述程序，控制台将输出：

[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]

总结

通过本篇 Java编程教程，你已经掌握了如何使用递归和回溯法实现全排列算法。这种递归实现排列的方式逻辑清晰、易于理解，是解决组合类问题的基础。建议你动手敲一遍代码，加深理解。未来你还可以扩展此方法，用于处理含重复元素的排列、部分排列等问题。

掌握 Java排列生成，是你迈向算法高手的重要一步！