Java數組組合與排列的高效生成
本文介紹如何高效生成Java數組中所有至少包含兩個元素的組合和排列。例如,給定數組[11, 33, 22],我們需要找出所有可能的組合,例如[11, 33]、[11, 22]、[11, 33, 22]等,并且要區分元素順序,例如[11, 33]和[33, 11]視為不同的結果。
高效的解決方案是結合遞歸和排列算法。以下代碼演示了這種方法:
import java.util.*; public class CombinationPermutation { public static void main(String[] args) { int[] nums = {11, 33, 22}; generateCombinationsAndPermutations(nums); } public static void generateCombinationsAndPermutations(int[] nums) { for (int i = 2; i <= nums.length; i++) { List<List<Integer>> combinations = combine(nums, i); for (List<Integer> combination : combinations) { permute(combination, 0); } } } // 生成組合 public static List<List<Integer>> combine(int[] nums, int k) { List<List<Integer>> result = new ArrayList<>(); List<Integer> current = new ArrayList<>(); backtrack(nums, result, current, 0, k); return result; } private static void backtrack(int[] nums, List<List<Integer>> result, List<Integer> current, int start, int k) { if (current.size() == k) { result.add(new ArrayList<>(current)); return; } for (int i = start; i < nums.length; i++) { current.add(nums[i]); backtrack(nums, result, current, i + 1, k); current.remove(current.size() - 1); } } // 生成排列 public static void permute(List<Integer> nums, int l) { if (l == nums.size()) { System.out.println(nums); return; } for (int i = l; i < nums.size(); i++) { Collections.swap(nums, l, i); permute(nums, l + 1); Collections.swap(nums, l, i); // 回溯 } } }
這段代碼首先使用combine函數生成所有可能的組合,然后使用permute函數對每個組合進行全排列。combine函數使用遞歸回溯法,permute函數也使用遞歸,通過交換元素實現全排列。 通過循環控制組合的長度(從2到數組長度),確保所有至少包含兩個元素的組合都被考慮。 該方法在處理較大數組時效率較高。
? 版權聲明
文章版權歸作者所有,未經允許請勿轉載。
THE END