java如何实现排列组合算法

47次阅读
没有评论

共计 1196 个字符,预计需要花费 3 分钟才能阅读完成。

在 Java 中可以使用递归来实现排列组合算法。以下是一个示例代码:

import java.util.ArrayList;
import java.util.List;
public class Combination {public static void main(String[] args) {List nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(4);
int r = 3; // 选择 r 个元素进行组合
List<List> combinations = combine(nums, r);
for (List combination : combinations) {for (int num : combination) {System.out.print(num + " ");
}
System.out.println();}
}
public static List<List> combine(List nums, int r) {List<List> result = new ArrayList();
List path = new ArrayList();
dfs(nums, r, 0, path, result);
return result;
}
private static void dfs(List nums, int r, int start, List path, List<List> 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 个元素进行排列组合的结果。

丸趣 TV 网 – 提供最优质的资源集合!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-12-20发表,共计1196字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)