集合元素的排列与组合

个人算法练习总结贴

Posted by Jeremy Song on 2022-05-25
Estimated Reading Time 2 Minutes
Words 686 In Total
Viewed Times

最近因为算法考试,一直就是有空闲了刷刷题。
刷的题多了,也就发现很多基础算法在一些较复杂的题中都有应用,比如这篇文章中将要提到的排列和组合。

排列

排列,一般地,从m个不同元素中取出n(n≤m)个元素,按照一定的顺序排成一列,叫做从m个元素中取出n个元素的一个排列(permutation)。

组合

组合,一般地,从m个不同的元素中,任取n(n≤m)个元素为一组,叫作从m个不同元素中取出n个元素的一个组合。

区别

以上两个概念在高中数学中就学习,此处就不过多的阐述。 唯一强调一下二者的差异,排列是有序的,组合是无序的

代码实现样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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++;
}
}

欢迎关注我的公众号 须弥零一,跟我一起学习IT知识。


如果您喜欢此博客或发现它对您有用,则欢迎对此发表评论。 也欢迎您共享此博客,以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权,请与作者联系以将其删除。 谢谢 !