集合元素的排列与组合
最近因为算法考试，一直就是有空闲了刷刷题。 刷的题多了，也就发现很多基础算法在一些较复杂的题中都有应用，比如这篇文章中将要提到的排列和组合。
排列
排列，一般地，从m个不同元素中取出n（n≤m）个元素，按照一定的顺序排成一列，叫做从m个元素中取出n个元素的一个排列(permutation)。
组合
组合，一般地，从m个不同的元素中，任取n（n≤m）个元素为一组，叫作从m个不同元素中取出n个元素的一个组合。
区别
以上两个概念在高中数学中就学习，此处就不过多的阐述。 唯一强调一下二者的差异，排列是有序的，组合是无序的
代码实现样例
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
/**
* 排列与组合的基本算法
*/
public class ArrangeAndCombination {
private static int m, n, COUNT;
/**
* 测试入口
*/
public static void main(String[] args) {
m = 10;
n = 3;
// 从10个元素中取三个元素有多少种取法？
COUNT = 0;
nCm(1, new HashSet<>());
System.out.println("=== 组合 ===");
System.out.println(COUNT);
// 从10个元素中取三个并排序有多少种情况？
COUNT = 0;
nAm(new ArrayList<>());
System.out.println("=== 排列 ===");
System.out.println(COUNT);
}
/**
* 组合算法
* @param start 元素选择的起始位置
* @param selected 已选中的元素
*/
private static void nCm(int start, Set<Integer> selected) {
if (selected.size() == n) { // 已选中的数量满足要求，打印结果并退出函数
printResult(selected);
return;
}
// 已选中的数量不足，则继续选择元素
for (int i = 1; i <= m; i++) {
selected.add(i); // 选择当前元素
nCm(i + 1, selected); // 下一个元素的选择从当前元素的下一个开始
selected.remove(i); // 移除当前元素
}
}
/**
* 排列算法
* @param selected 已选中的元素
*/
private static void nAm(List<Integer> selected) {
if (selected.size() == n) { // 已选中的数量满足要求，打印结果并退出函数
printResult(selected);
return;
}
// 已选中的数量不足，则继续选择元素
for (int i = 1; i <= m; i++) {
if (!selected.contains(i)) { // 已选中的元素不能再次选择
selected.add(i); // 选中当前元素
nAm(selected); // 选择下一个元素
selected.remove((Object) i); // 移除当前元素。注意List#remove(Object)才是移除元素的函数，变量i要强转
}
}
}
/**
* 打印结果并计数
* @param selected 已选中的元素
*/
private static void printResult(Collection<Integer> selected) {
StringBuilder sb = new StringBuilder();
selected.forEach(x -> sb.append(",").append(x));
System.out.println(sb.substring(1)); // 移除第一个,号
COUNT++;
}
}原文：https://www.jeremysong.cn/cn/arrange-and-combination/
欢迎关注我的公众号“须弥零一”，更多技术文章第一时间推送。
评论