阅读量:0
在Java中可以使用递归来实现排列组合算法。以下是一个示例代码:
import java.util.ArrayList; import java.util.List; public class Combination { public static void main(String[] args) { List<Integer> nums = new ArrayList<>(); nums.add(1); nums.add(2); nums.add(3); nums.add(4); int r = 3; // 选择r个元素进行组合 List<List<Integer>> combinations = combine(nums, r); for (List<Integer> combination : combinations) { for (int num : combination) { System.out.print(num + " "); } System.out.println(); } } public static List<List<Integer>> combine(List<Integer> nums, int r) { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(nums, r, 0, path, result); return result; } private static void dfs(List<Integer> nums, int r, int start, List<Integer> path, List<List<Integer>> result) { if (path.size() == r) { result.add(new ArrayList<>(path)); return; } for (int i = start; i < nums.size(); i++) { path.add(nums.get(i)); dfs(nums, r, i + 1, path, result); path.remove(path.size() - 1); } } }
上述代码使用了深度优先搜索(DFS)的方式来生成排列组合。首先定义了一个combine
方法,接收一个包含元素的列表和选择的元素个数r
作为参数。在combine
方法中,创建了一个结果列表result
和一个路径列表path
。然后调用dfs
方法进行深度优先搜索。
dfs
方法接收了待选择的元素列表nums
、选择的元素个数r
、当前搜索的起始位置start
、当前路径path
和结果列表result
作为参数。首先判断当前路径的长度是否等于选择的元素个数r
,如果是,则将当前路径加入结果列表,并返回。否则,从起始位置start
开始遍历待选择的元素列表nums
,将当前元素加入路径列表path
,然后递归调用dfs
方法继续搜索下一个元素,搜索的起始位置为当前位置的下一个位置i + 1
。当递归返回后,将当前元素从路径列表中移除,继续遍历下一个元素。最后,返回结果列表。
运行上述代码,输出结果为:
1 2 3 1 2 4 1 3 4 2 3 4
这就是给定列表中选择3个元素进行排列组合的结果。