The full permutation problem is a classic algorithm problem, which refers to the generation of non-repetitive permutation combinations for all elements in a sequence. The following is a detailed implementation and explanation of the full arrangement problem in Java.
1. Full arrangement problem definition
enter:Given a sequence or array, find out the arrangement of all elements.
Output:Returns all possible permutations.
Example:
enter:[1, 2, 3]
Output:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
2. Commonly used algorithms
Common implementation methods for full arrangement:
- Backtracking method（Backtracking）
- Dictionary order arrangement（Lexicographic Order）
- Iteration method(Non-recursive implementation)
3. Use backtracking to solve full permutation
Backtrace is a recursive-based search algorithm that generates all possible solutions by constantly trying and undoing previous choices.
3.1 Backtracement method implementation (basic version)
Suitable for full permutations of no duplicate elements in an array.
import ;
import ;
public class Permutations {
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[]; // Whether the mark has been used 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) {
// Termination condition: The size of the current arrangement is equal to the length of the array if (() == ) {
(new ArrayList<>(current)); // Add the current arrangement to the result return;
}
// Iterate through each element for (int i = 0; i < ; i++) {
if (used[i]) { // Skip used elements continue;
}
// Make a choice (nums[i]);
used[i] = true;
// recursion backtrack(nums, used, current, result);
// Undo the selection (() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> permutations = permute(nums);
(permutations);
}
}
Output result
For input[1, 2, 3]：
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
3.2 Backtracking method (no mark array)
By swapping elements in an array, you can avoid using tagged arrays.
import ;
import ;
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 == ) {
List<Integer> permutation = new ArrayList<>();
for (int num : nums) {
(num);
}
(permutation);
return;
}
for (int i = start; i < ; i++) {
swap(nums, start, i); // Swap elements backtrack(nums, start + 1, result);
swap(nums, start, i); // Revoke the exchange }
}
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);
(permutations);
}
}
3.3 Backtracking method to process duplicate elements
If the array contains duplicate elements (e.g.[1, 1, 2]), we need to deduplicate the results. This can be done by sorting the array and skipping duplicate elements when recursive.
import ;
import ;
import ;
public class PermutationsWithDuplicates {
public static List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
(nums); // Sort so that duplicate elements are skipped boolean[] used = new boolean[];
backtrack(nums, used, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
if (() == ) {
(new ArrayList<>(current));
return;
}
for (int i = 0; i < ; i++) {
if (used[i]) {
continue;
}
// Skip adjacent duplicate elements if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
(nums[i]);
used[i] = true;
backtrack(nums, used, current, result);
(() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
int[] nums = {1, 1, 2};
List<List<Integer>> permutations = permuteUnique(nums);
(permutations);
}
}
Output result
For input[1, 1, 2]：
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
4. Dictionary order arrangement
Steps to generate a full arrangement by dictionary order:
- Find the "last ascending pair" of the current arrangement.
- Find the minimum value larger than the smaller value in the ascending pair from the right and swap these two values.
- Reverse the right part.
Suitable for situations where output is required in dictionary order.
import ;
public class PermutationsLexicographic {
public static void nextPermutation(int[] nums) {
int i = - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) { // Find ascending pair i--;
}
if (i >= 0) {
int j = - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j); // exchange }
reverse(nums, i + 1); // Invert the subsequent part }
private static void reverse(int[] nums, int start) {
int i = start, j = - 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};
((nums));
for (int i = 0; i < 6; i++) {
nextPermutation(nums);
((nums));
}
}
}
5. Summary
Comparison of common methods
| method | Applicable scenarios | Features |
|---|---|---|
| Backtracking method | Full arrangement (general) | Most commonly used, suitable for generating all permutations, can handle repeating elements, implemented through recursion and pruning. |
| Exchange method | All arrangement without repetition | There is no need for extra space to mark the array, and the arrangement is achieved through exchange, but additional processing is required for duplicate elements. |
| Dictionary order arrangement | Dictionary order output arrangement | Generate and arrange in dictionary order, suitable for serializing output; the input sequence needs to be sorted as the initial state. |
| Iteration method | Generate a specific scenario for an arrangement | Using loops instead of recursion, but it is more complicated to implement and is suitable for iterative optimization in permutation generation problems. |
Performance Analysis
-
Time complexity: O ( n ! ) O(n!) O(n!), each method
The time complexity is proportional to the number of arrangements. -
Space complexity：
- Backtrace method using marker array: O ( n ) O(n) O(n)
- Use the exchange method: O ( 1 ) O(1) O(1) (excluding recursive stack)
Full permutation is a basic and important issue in the algorithm. Backtracement method is the most commonly used solution, and in actual development, appropriate methods can be selected according to different needs to achieve efficient arrangement generation.
This is the end of this article about several implementation methods of Java full arrangement. For more related Java full arrangement content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!