我要评论全排列问题是一个经典的算法问题，指的是对一个序列中的所有元素生成不重复的排列组合。以下是全排列问题在 java 中的详细实现和讲解。
1. 全排列问题定义
输入： 给定一个序列或数组，找出所有元素的排列。
输出： 返回所有可能的排列。
示例：
输入：[1, 2, 3]
输出：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
2. 常用算法
全排列的常见实现方法：
- 回溯法（backtracking）
- 字典序排列法（lexicographic order）
- 迭代法（非递归实现）
3. 使用回溯法解决全排列
回溯法是一种基于递归的搜索算法，它通过不断尝试并撤销之前的选择来生成所有可能的解。
3.1 回溯法实现（基础版）
适用于数组中无重复元素的全排列。
import java.util.arraylist;
import java.util.list;
public class permutations {
public static list<list<integer>> permute(int[] nums) {
list<list<integer>> result = new arraylist<>();
boolean[] used = new boolean[nums.length]; // 标记是否使用过
list<integer> current = new arraylist<>();
backtrack(nums, used, current, result);
return result;
}
private static void backtrack(int[] nums, boolean[] used, list<integer> current, 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]) { // 跳过已使用的元素
continue;
}
// 做选择
current.add(nums[i]);
used[i] = true;
// 递归
backtrack(nums, used, current, result);
// 撤销选择
current.remove(current.size() - 1);
used[i] = false;
}
}
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, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
3.2 回溯法（不使用标记数组）
通过交换数组中的元素，可以避免使用标记数组。
import java.util.arraylist;
import java.util.list;
public class permutationsswap {
public static list<list<integer>> permute(int[] nums) {
list<list<integer>> 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;
}
for (int i = start; i < nums.length; 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);
}
}
3.3 回溯法处理重复元素
如果数组中包含重复元素（例如 [1, 1, 2]），我们需要对结果去重。可以通过对数组排序并在递归时跳过重复元素来实现。
import java.util.arraylist;
import java.util.arrays;
import java.util.list;
public class permutationswithduplicates {
public static list<list<integer>> permuteunique(int[] nums) {
list<list<integer>> result = new arraylist<>();
arrays.sort(nums); // 排序以便跳过重复元素
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new arraylist<>(), result);
return result;
}
private static void backtrack(int[] nums, boolean[] used, list<integer> current, 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]) {
continue;
}
// 跳过相邻重复的元素
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
current.add(nums[i]);
used[i] = true;
backtrack(nums, used, current, result);
current.remove(current.size() - 1);
used[i] = false;
}
}
public static void main(string[] args) {
int[] nums = {1, 1, 2};
list<list<integer>> permutations = permuteunique(nums);
system.out.println(permutations);
}
}
输出结果
对于输入[1, 1, 2]：
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
4. 字典序排列法
字典序法生成全排列的步骤：
- 找到当前排列的“最后一个升序对”。
- 从右侧找到比升序对中较小值大的最小值，交换这两个值。
- 将右侧部分反转。
适用于需要按字典序输出排列的情况。
import java.util.arrays;
public class permutationslexicographic {
public static void nextpermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) { // 找到升序对
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j); // 交换
}
reverse(nums, i + 1); // 反转后面的部分
}
private static void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
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};
system.out.println(arrays.tostring(nums));
for (int i = 0; i < 6; i++) {
nextpermutation(nums);
system.out.println(arrays.tostring(nums));
}
}
}
5. 总结
常见方法对比
| 方法 | 适用场景 | 特点 |
|---|---|---|
| 回溯法 | 全排列（通用） | 最常用，适合生成所有排列，可以处理重复元素，通过递归和剪枝实现。 |
| 交换法 | 无重复全排列 | 不需要额外空间标记数组，通过交换实现排列，但对重复元素需要额外处理。 |
| 字典序排列法 | 字典序输出排列 | 按字典序生成排列，适合序列化输出；需要对输入序列进行排序作为初始状态。 |
| 迭代法 | 生成排列的特定场景 | 使用循环代替递归，但实现起来较为复杂，适合排列生成问题中的迭代优化。 |
性能分析
- 时间复杂度： o ( n ! ) o(n!) o(n!)，每种方法
的时间复杂度都与排列数量成正比。 - 空间复杂度：
- 使用标记数组的回溯法： o ( n ) o(n) o(n)
- 使用交换法： o ( 1 ) o(1) o(1)（不包括递归栈）
全排列是算法中基础而重要的问题。回溯法是最常用的解决方式，而在实际开发中，根据不同的需求可以选择合适的方法来实现高效的排列生成。
到此这篇关于java 全排列的几种实现方法的文章就介绍到这了,更多相关java 全排列内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论