Java实现全排列的三种算法详解

全排列是一种非常常见的排列问题，即给定一个数组，需要将其所有元素进行全排列，即将数组中的元素进行全排列得到新的数组。

下面介绍三种常见的全排列算法的实现。

1.递归算法：

递归算法是一种非常直观的全排列算法，其基本思想是将数组中的第一个元素与其它元素进行交换，然后对剩余的元素进行全排列，直到只剩下一个元素为止。

具体实现如下：

public class Permutations {
public static void main(String[] args) {
int[] nums = {1, 2, 3};
permute(nums);
}
public static void permute(int[] nums) {
permute(nums, 0, nums.length - 1);
}
private static void permute(int[] nums, int l, int r) {
if (l == r) {
printArray(nums);
} else {
for (int i = l; i <= r; i++) {
swap(nums, l, i);
permute(nums, l + 1, r);
swap(nums, l, i); // 还原数组
}
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static void printArray(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println();
}
}

2.字典序算法：

字典序算法是另一种常见的全排列算法，其基本思想是通过字典序来生成全排列。首先将数组按照字典序排序，然后不断生成下一个排列，直到所有的排列都生成完毕。

具体实现如下：

public class Permutations {
public static void main(String[] args) {
int[] nums = {1, 2, 3};
permute(nums);
}
public static void permute(int[] nums) {
Arrays.sort(nums);
printArray(nums);
while (nextPermutation(nums)) {
printArray(nums);
}
}
private static boolean 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 (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
return i >= 0;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
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 printArray(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println();
}
}

3.回溯算法：

回溯算法是一种非常灵活的全排列算法，其基本思想是通过递归的方式生成全排列。具体实现如下：

public class Permutations {
public static void main(String[] args) {
int[] nums = {1, 2, 3};
permute(nums);
}
public static void permute(int[] nums) {
List> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums);
for (List list : result) {
printList(list);
}
}
private static void backtrack(List> result, List tempList, int[] nums) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (tempList.contains(nums[i])) {
continue;
}
tempList