Java 全排列的幾種實現(xiàn)方法
全排列問題是一個經(jīng)典的算法問題,指的是對一個序列中的所有元素生成不重復(fù)的排列組合。以下是全排列問題在 Java 中的詳細(xì)實現(xiàn)和講解。
1. 全排列問題定義
輸入: 給定一個序列或數(shù)組,找出所有元素的排列。
輸出: 返回所有可能的排列。
示例:
輸入:[1, 2, 3]
輸出:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
2. 常用算法
全排列的常見實現(xiàn)方法:
- 回溯法(Backtracking)
- 字典序排列法(Lexicographic Order)
- 迭代法(非遞歸實現(xiàn))
3. 使用回溯法解決全排列
回溯法是一種基于遞歸的搜索算法,它通過不斷嘗試并撤銷之前的選擇來生成所有可能的解。
3.1 回溯法實現(xiàn)(基礎(chǔ)版)
適用于數(shù)組中無重復(fù)元素的全排列。
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]; // 標(biāo)記是否使用過 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) { // 終止條件:當(dāng)前排列的大小等于數(shù)組長度 if (current.size() == nums.length) { result.add(new ArrayList<>(current)); // 將當(dāng)前排列加入結(jié)果 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); } }
輸出結(jié)果
對于輸入 [1, 2, 3]
:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
3.2 回溯法(不使用標(biāo)記數(shù)組)
通過交換數(shù)組中的元素,可以避免使用標(biāo)記數(shù)組。
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 回溯法處理重復(fù)元素
如果數(shù)組中包含重復(fù)元素(例如 [1, 1, 2]
),我們需要對結(jié)果去重。可以通過對數(shù)組排序并在遞歸時跳過重復(fù)元素來實現(xiàn)。
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); // 排序以便跳過重復(fù)元素 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; } // 跳過相鄰重復(fù)的元素 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); } }
輸出結(jié)果
對于輸入[1, 1, 2]
:
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
4. 字典序排列法
字典序法生成全排列的步驟:
- 找到當(dāng)前排列的“最后一個升序?qū)?rdquo;。
- 從右側(cè)找到比升序?qū)χ休^小值大的最小值,交換這兩個值。
- 將右側(cè)部分反轉(zhuǎn)。
適用于需要按字典序輸出排列的情況。
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]) { // 找到升序?qū)? 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); // 反轉(zhuǎn)后面的部分 } 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. 總結(jié)
常見方法對比
方法 | 適用場景 | 特點 |
---|---|---|
回溯法 | 全排列(通用) | 最常用,適合生成所有排列,可以處理重復(fù)元素,通過遞歸和剪枝實現(xiàn)。 |
交換法 | 無重復(fù)全排列 | 不需要額外空間標(biāo)記數(shù)組,通過交換實現(xiàn)排列,但對重復(fù)元素需要額外處理。 |
字典序排列法 | 字典序輸出排列 | 按字典序生成排列,適合序列化輸出;需要對輸入序列進(jìn)行排序作為初始狀態(tài)。 |
迭代法 | 生成排列的特定場景 | 使用循環(huán)代替遞歸,但實現(xiàn)起來較為復(fù)雜,適合排列生成問題中的迭代優(yōu)化。 |
性能分析
- 時間復(fù)雜度: O ( n ! ) O(n!) O(n!),每種方法
的時間復(fù)雜度都與排列數(shù)量成正比。 - 空間復(fù)雜度:
- 使用標(biāo)記數(shù)組的回溯法: O ( n ) O(n) O(n)
- 使用交換法: O ( 1 ) O(1) O(1)(不包括遞歸棧)
全排列是算法中基礎(chǔ)而重要的問題?;厮莘ㄊ亲畛S玫慕鉀Q方式,而在實際開發(fā)中,根據(jù)不同的需求可以選擇合適的方法來實現(xiàn)高效的排列生成。
到此這篇關(guān)于Java 全排列的幾種實現(xiàn)方法的文章就介紹到這了,更多相關(guān)Java 全排列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
字節(jié)碼調(diào)教入口JVM?寄生插件javaagent
這篇文章主要介紹了字節(jié)碼調(diào)教入口JVM?寄生插件javaagent方法示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08使用原生JDBC動態(tài)解析并獲取表格列名和數(shù)據(jù)的方法
這篇文章主要介紹了使用原生JDBC動態(tài)解析并獲取表格列名和數(shù)據(jù),本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-08-08Mybatis如何獲取insert新增數(shù)據(jù)id值
這篇文章主要介紹了Mybatis如何獲取insert新增數(shù)據(jù)id值問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05Java.toCharArray()和charAt()的效率對比分析
這篇文章主要介紹了Java.toCharArray()和charAt()的效率對比分析,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-10-10Java三種獲取redis的連接及redis_String類型演示(適合新手)
這篇文章主要介紹了Java三種獲取redis的連接及redis_String類型演示(適合新手),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12