| 排列數(shù) A(n, m) 與組合數(shù) C(n, m) 的求法 | 您所在的位置：網(wǎng)站首頁(yè) › 八字的排列組有多少種算法 › 排列數(shù) A(n, m) 與組合數(shù) C(n, m) 的求法 |
排列數(shù) A(n, m) 與組合數(shù) C(n, m) 的求法
|
一、什么是排列，什么是組合？
排列
從 n 個(gè)不同元素中，任取 m(m≤n) 個(gè)元素，按照一定的順序排成一列，叫做從 n 個(gè)不同元素中取出 m 個(gè)元素的一個(gè)排列。 組合從 n 個(gè)不同元素中，任取 m(m≤n）個(gè)元素并成一組，叫做從 n 個(gè)不同元素中取出 m 個(gè)元素的一個(gè)組合。 通俗地講 A (排列)：指把幾個(gè)不但選出來(lái)，還要進(jìn)行排列 如 A42A_4^2A42? 是指從 4 個(gè)物品中選出 2 個(gè)來(lái)，而且對(duì)它們的順序是有要求的，順序不一樣，結(jié)果則不一樣。A42=4×3=12A_4^2 =4×3=12A42?=4×3=12 C (組合)：是指從 n 個(gè)數(shù)中選取幾個(gè)出來(lái)，不排列，只組合。如 C42C_4^2C42? 是指從 4 個(gè)中選 2 個(gè)，不管它們的內(nèi)部的順序。C42=C_4^2 =C42?= 4×32×1=6\cfrac{4×3}{2×1} = 62×14×3?=6. 總結(jié)：排列與元素的順序有關(guān)，組合與順序無(wú)關(guān)。如 231 與 213 是兩個(gè)排列；2+3+1 的和與 2+1+3 的和是一個(gè)組合。
m 就是需要減 1 的次數(shù)。 int A(int n, int m) { int res = 1; for (int i = m; i >= 1; i--) { res *= n; //n × n-1 × n-2 × ... n-m，m就是需要減1的次數(shù) n--; } } (2) 組合數(shù)與求排列數(shù)一樣，求組合數(shù)也是對(duì)公式的實(shí)現(xiàn)，不過(guò)組合這里有個(gè)小技巧可以對(duì)代碼進(jìn)行優(yōu)化，那就是利用組合的互補(bǔ)率：Cnm=Cnn?mC_n^m = C_n^{ n - m}Cnm?=Cnn?m? 來(lái)減少循環(huán)執(zhí)行次數(shù)。 版本一由上可得 Cnm=C_n^m=Cnm?= Anmm!\cfrac{A_n^m}{m!}m!Anm??，而 m!m!m! =Amm=A_m^m=Amm?，故代碼可表達(dá)為： int C(int n, int m) { m = Math.min(m, n-m); int numerator = A(n, m); //分子 int denominator = A(m, m); //分母 return numerator / denominator; } 版本二根據(jù) Cnm=C_n^m=Cnm?= Anmm!\cfrac{A_n^m}{m!}m!Anm??，但我們注意到，AnmA_n^mAnm? 的代碼實(shí)現(xiàn)中，m 一直遍歷到 1，所以在方法 A() 的代碼實(shí)現(xiàn)中我們簡(jiǎn)單的加入對(duì) m!m!m! 的求解即可，不需要為了求組合數(shù)還得多寫(xiě)一個(gè)求排列數(shù)的函數(shù)。 int A(int n, int m) { int up = 1; //分子 int down = 1; //分母 m = Math.min(m, n-m); for (int i = m; i >= 1; i--) { up *= n; //累乘得到分子 n--; down *= i; //累乘得到分母 } return up / down; } |
由上可得，排列數(shù)和組合數(shù)的求法代碼如下：【本文地址】
公司簡(jiǎn)介
聯(lián)系我們