數學問題 - 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