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
