数学问题 - java实现排列组合
今天遇到一个组合问题，整理学习相关数学算法问题，并做记录。
如果和我一样已经忘记数学集合，排列组合问题的，就需要先看下排列组合推导，及公式。
排列公式：A(n,m)=n!/(n-m)!
组合公式：C(n,m)=n!/m!(n-m)!
二项式定理：非空子集=2^n -1
目录
数学问题 - java实现排列组合
一、放回再取问题
二、排列问题
三、组合问题
总结：
一、放回再取问题
问题1：
假设袋子里有编号为1,2,...,m这m个球。现在每次从袋子中取一个球几下编号，放回袋中再取，取n次作为一组，枚举所有可能的情况。
分析：
每一次取都有m种可能的情况，因此一共有
种情况。
// 问题1：
// 假设袋子里有编号为1,2,...,m这m个球。现在每次从袋子中取一个球几下编号，放回袋中再取，取n次作为一组，枚举所有可能的情况。
//
// 分析：
// 每一次取都有m种可能的情况，因此一共有种情况。
//看第一个问题, 有1,2,3,4这4个数字.可以重复的在里面选3次,问能得到多少种结果
//栈 先进后出，数组的数据模型
static Stack<Integer> stack = new Stack<Integer>();
static int cnt = 0;
@Test
public void testRecursion() {
int[] data = {1, 2, 3};
recursion(data, 0, 3);
System.out.println(cnt);
}
/**
* 递归方法，当实际选取的数目与要求选取的小目相同时，跳出递归
*
* @param array - 数组
* @param curnum - 当前已经确定的个数
* @param maxnum - 要选取的数目
*/
public static void recursion(int[] array, int curnum, int maxnum) {
if (curnum == maxnum) {
cnt++;
System.out.println(stack);
return;
}
for (int item : array) {
stack.push(item);
recursion(array, curnum + 1, maxnum);
stack.pop();
}
}
打印结果
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]
27
二、排列问题
问题2：
假设袋子里有编号为1,2,...,m这m个球。先后从袋子中取出n个球，依次记录编号，枚举所有可能的情况。
分析：
这是排列问题，应该有
种情况。
// 问题2：
// 假设袋子里有编号为1,2,...,m这m个球。先后从袋子中取出n个球，依次记录编号，枚举所有可能的情况。
static Stack<Integer> stack = new Stack<Integer>();
static int cnt = 0;
@Test
public void testRecursion2() {
int[] data = {1, 2, 3};
recursion2(data, 0, 3);
System.out.println(cnt);
}
public static void recursion2(int[] array, int curnum, int maxnum) {
if (curnum == maxnum) {
cnt++;
System.out.println(stack);
return;
}
for (int item : array) {
if (!stack.contains(item)) {
stack.push(item);
recursion2(array, curnum + 1, maxnum);
stack.pop();
}
}
}
打印结果：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
6
三、组合问题
问题3：
从m个球里（编号为1,2,3...,m）一次取n个球，其中m>n，记录取出球的编号，枚举所有的可能性。
分析：
这是组合问题。因该有
种可能性。
// 问题3：
// 从m个球里（编号为1,2,3...,m）一次取n个球，其中m>n，记录取出球的编号，枚举所有的可能性
static Stack<Integer> stack = new Stack<Integer>();
static int cnt = 0;
@Test
public void testRecursion3() {
int[] data = {1, 2, 3, 4};
recursion3(data, 0, 3, 0);
System.out.println(cnt);
}
public static void recursion3(int[] array, int curnum, int maxnum, int indexnum) {
if (curnum == maxnum) {
cnt++;
System.out.println(stack);
return;
}
for (int i = indexnum; i < array.length; i++) {
if (!stack.contains(array[i])) {
stack.push(array[i]);
recursion3(array, curnum + 1, maxnum, i);
stack.pop();
}
}
}
打印结果：
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
4
总结：
1、数学问题，排列组合
2、递归思想
3、巧妙的运用了栈stack
java中的栈stack https://blog.csdn.net/xinpz/article/details/109642137
参考：
https://www.cnblogs.com/zzlback/p/10947064.html
https://blog.csdn.net/Ring_k/article/details/79575533