組合演算法教程
⑴ 排列組合公式及排列組合演算法
排列組合公式
排列組合公式/排列組合計算公式
公式P是指排列，從N個元素取M個進行排列。
公式C是指組合，從N個元素取M個進行組合，不進行排列。
N-元素的總個數
M參與選擇的元素個數
！-階乘，如9！＝9*8*7*6*5*4*3*2*1
從N到數M個，表達式應該為n*（n-1)*(n-2)..(n-m+1);
因為從n到（n-m+1)個數為n－(n-m+1)＝m
舉例：
Q1: 有從1到9共計9個號碼球，請問，可以組成多少個三位數？
A1: 123和213是兩個不同的排列數。即對排列順序有要求的，既屬於「排列P」計算范疇。
上問題中，任何一個號碼只能用一次，顯然不會出現988,997之類的組合，我們可以這么看，百位數有9種可能，十位數則應該有9-1種可能，個位數則應該只有9-1-1種可能，最終共有9*8*7個三位數。計算公式＝P(3,9)＝9*8*7,(從9倒數3個的乘積）
Q2:有從1到9共計9個號碼球，請問，如果三個一組，代表「三國聯盟」，可以組合成多少個「三國聯盟」？
A2:213組合和312組合，代表同一個組合，只要有三個號碼球在一起即可。即不要求順序的，屬於「組合C」計算范疇。
上問題中，將所有的包括排列數的個數去除掉屬於重復的個數即為最終組合數C(3,9)=9*8*7/3*2*1
⑵ 排列組合中A和C怎麼算啊
1、排列組合中，組合的計算公式為：
⑶ 組合數公式的演算法舉例
1、設15000件產品中有1000件次品，從中拿出150件，求得到次品數的期望和方差？
2、設某射手對同一目標射擊，直到射中R次為止，記X為使用的射擊次數，已知命中率為P，求E（X）、D（X）。
這兩題都要用到一些技巧。我先列出幾個重要公式，證明過程中提供變換技巧，然後把這兩個題目作為例題。
先定義一個符號，用S（K=1，N）F（K）表示函數F（K）從K=1到K=N求和。
公式1：
C（M-1，N-1）+C（M-1，N）=C（M，N）
公式1 證明：
方法1、可直接利用組合數的公式證明。
方法2、（更重要的思路）。
從M個元素中任意指定一個元素。則選出N個的方法中，包含這一個元素的有C（M-1，N-1）種組合，不包含這一個元素的有C（M-1，N）種組合。
因此，C（M-1，N-1）+C（M-1，N）=C（M，N）
公式2：
S（K=N，M）C（K-1，N-1）=C（M，N） （M》=N）
證明：C（M，N）是從M個物品中任選N個的方法。
從M個物品中任意指定M-N個，並按次序編號為第1到第M-N號，而其餘的還有N個。
則選出N個的方法可分類為：
包含1號的有C（M-1，N-1）種；
不包含1號，但包含2號的有C（M-2，N-1）種；
。。。。。。
不包含1到M-K號，但包含M-K+1號的有C（K-1，N-1）種
。。。。。。
不包含1到M-N-1號，但包含M-N號的有C（N，N-1）種不包含1到M-N號的有C（N，N）種，而C（N，N）=C（N-1，N-1）
由於兩種思路都是從M個物品中任選N個的方法，因此
S（K=N，M）C（K-1，N-1）=C（M，N）
公式3：
S（K=0，N）C（P，K）*C（Q，N-K）=C（P+Q，N） （P，Q）=N）
證明：一批產品包含P件正品和Q件次品，則從這批產品中任選N件的選法為C（P+Q，N）。而公式裡面的K表示選法中正品數量，
C（P，K）*C（Q，N-K）表示N件產品中有K件正品，N-K件次品的選法。K從0到N變化時，就包含了所有不同正品、次品數的組合。
因此，S（K=0，N）C（P，K）*C（Q，N-K）=C（P+Q，N）
公式4（一種變換技巧）：
S（K=0，N）K*C（M，K）=S（K=0，N-1）M*C（M-1，K）
證明：
S（K=0，N）K*C（M，K）
=S（K=1，N）K*C（M，K）
=S（K=1，N）K*M！/K！/（M-K）！
=S（K=1，N）M*（M-1）！/（K-1）！/（M-K）！
=S（K=1，N）M*C（M-1，K-1）
=S（K=0，N-1）M*C（M-1，K）
公式5（公式4的同種）
S（K=0，N）K*（K-1）*C（M，K）
=S（K=0，N-2）M*（M-1）*C（M-2，K）
證明：（類似上式）
S（K=0，N）K*（K-1）*C（M，K）
=S（K=2，N）K*（K-1）*M！/K！/（M-K）！
=S（K=2，N）M*（M-1）*（M-2）！/（K-2）！/（M-K）！
=S（K=2，N）M*（M-1）*C（M-2，K-2）
=S（K=0，N-2）M*（M-1）*C（M-2，K）
公式4用於求數學期望，公式4、公式5結合起來可用於求方差。
例1、設15000件產品中有1000件次品，從中拿出150件，求得到次品數的期望和方差？
解：（本題利用公式3、4、5）
有K件次品的概率為：
P（K）=C（1000，K）*C（14000，150-K）/C（15000，150）
E（X）
=S（K=0，150）K*C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，149）1000*C（999，K）*（14000，149-K）/C（15000，150）
=1000*C（14999，149）/C（15000，150）
=10
D（X）
=S（K=0，150）（K-10）*（K-10）*C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，150）（K*K-K-19*K+100）*C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，150）K*（K-1）*C（1000，K）*C（14000，150-K）/C（15000，150）
-19*S（K=0，150）K*C（1000，K）*C（14000，150-K）/C（15000，150）
+100*S（K=0，150）C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，148）1000*999*C（998，K）*C（14000，148-K）/C（15000，150）
-19*S（K=0，149）*1000*C（999，K）*C（14000，149-K）/C（15000，150）
+100*S（K=0，150）C（1000，K）*C（14000，150-K）/C（15000，150）
=1000*999*C（14998，148）/C（15000，150）
-19*1000*C（14999，149）/C（15000，150）+100
=138600/14999
=9.240616041
此題推廣形式為：
設M件產品中有P件次品，從中拿出N件（N《=P），求得到次品數的期望和方差？
E（X）=P*N/M
D（X）=P*（P-1）*C（M-2，N-2）/C（M，N）
+（1-2*P*N/M）*P*C（M-2，N-2）/C（M，N）+（P*N/M）^2
例2、設某射手對同一目標射擊，直到射中R次為止，記X為使用的射擊次數，已知命中率為P，求E（X）、D（X）。
解：射中R次，使用的射擊次數為K次(K>=R)，則前K-1次射中R-1次，第K次射中了，概率為：
P（K）=C（K-1，R-1）*P^R*(1-P)^(K-R)
(以下暫時用W表示無窮大）
射中R次，使用的射擊次數可為R次、R+1次...W次
因此S（K=R，W）P（K）=1 （這是概率的特點）
即：S（K=R，W）C（K-1，R-1）*P^R*(1-P)^(K-R)=1
以上證明的式子是另一個公式，即無論P，R是什麼數都成立，以下將應用這一公式。
E（X）
=S（K=R，W）K*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）K*（K-1）！/（R-1）！/（K-R）！*P^R*(1-P)^(K-R)
=S（K=R，W）R*K！/R！/（K-R）！*P^R*(1-P)^(K-R)
=S（K=R，W）R*C（K，R）*P^R*(1-P)^(K-R)
=R/P*S（K=R，W）C（K，R）*P^（R+1）*(1-P)^(K-R)
令K1=K+1，R1=R+1，則
E（X）=R/P*S（K1=R1，W）C（K1-1，R1-1）*P^R1*(1-P)^(K1-R1)
利用以上公式得
E（X）=P/R
D（X）
=S（K=R，W）（K-R/P）^2*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）（K*K-2*K*R/P+R*R/P/P）*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）[K*（K+1）-（K+2*K*R/P）+R*R/P/P]*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）[K*（K+1）*C（K-1，R-1）*P^R*(1-P)^(K-R)
-S（K=R，W）（K+2*K*R/P）*C（K-1，R-1）*P^R*(1-P)^(K-R)
+S（K=R，W）R*R/P/P*C（K-1，R-1）*P^R*(1-P)^(K-R)
=（推導過程同求E（X），略）
=R（R+1）/P/P-（2*R+P）*R/P/P+R*R/P/P
=（1-P）*R/P/P
⑷ 排列組合中A和C的演算法怎麼算的，查了百度都不會，求詳細點的謝謝（高中）
排列數 A(n,m) ----------即 字母A右下角n 右上角m,表示n取m的排列數
A(n,m)=n!/(n-m)!=n*(n-1)*(n-2)*……*(n-m+1)
A(n,m)等於從n 開始連續遞減的 m 個自然數的積
n取m的排列數 A(n,m) 等於從n 開始連續遞減的 m 個自然數的積
例: A(7,3)=7*6*5=210
組合數 C(n,m) ----------即 字母C右下角n 右上角m,表示n取m的排列數
C(n,m)=n!/(m!*(n-m)!)=n*(n-1)*(n-2)*……*(n-m+1)/(1*2*3*……*m)
C(n,m)等於(從n 開始連續遞減的 m 個自然數的積)除以(從1開始連續遞增的 m 個自然數的積)
n選m的組合數 C(n,m) 等於(從n 開始連續遞減的 m 個自然數的積)除以(從1開始連續遞增的 m 個自然數的積)
例: C(7,3)=7*6*5/(1*2*3)=35
⑸ 關於各種排列組合java演算法實現方法
一 利用二進制狀態法求排列組合 此種方法比較容易懂 但是運行喊隱頌效率不高 小數據排列組合可以使用
復制代碼 代碼如下: import java util Arrays;//利用二進制演算法進行全排列 //count : //count :
public class test { public static void main(String[] args) { long start=System currentTimeMillis(); count (); long end=System currentTimeMillis(); System out println(end start); } private static void count (){ int[] num=new int []{ }; for(int i= ;i<Math pow( );i++){ String str=Integer toString(i ); int sz=str length(); for(int j= ;j< sz;j++){ str=" "+str; } char[] temp=str toCharArray(); Arrays sort(temp); String gl=new String(temp); if(!gl equals(" ")){ continue; } String result=""; for(int m= ;m<str length();m++){ result+=num[Integer parseInt(str charAt(m)+"")]; } System out println(result); } } public static void count (){ int[] num=new int []{ }; int[] ss=new int []{ }; int[] temp=new int[ ]; while(temp[ ]< ){ temp[temp length ]++; for(int i=temp length ;i> ;i ){ if(temp[i]== ){ temp[i]= ; temp[i ]++; } } int []tt=temp clone(); Arrays sort(tt); if(!Arrays equals(tt ss)){ continue; } String result=""; for(int i= ;i<num length;i++){ result+=num[temp[i]]; } System out println(result); } } }
二 用遞歸的思想攜慧來求排列跟組合 代碼量比較大
復制代碼 代碼如下鄭鄭: package practice;import java util ArrayList; import java util List;
public class Test {
/** * @param args */ public static void main(String[] args) { // TODO Auto generated method stub Object[] tmp={ }; // ArrayList<Object[]> rs=RandomC(tmp); ArrayList<Object[]> rs=cmn(tmp ); for(int i= ;i<rs size();i++) { // System out print(i+"="); for(int j= ;j<rs get(i) length;j++) { System out print(rs get(i)[j]+" "); } System out println(); } }
// 求一個數組的任意組合 static ArrayList<Object[]> RandomC(Object[] source) { ArrayList<Object[]> result=new ArrayList<Object[]>(); if(source length== ) { result add(source); } else { Object[] psource=new Object[source length ]; for(int i= ;i<psource length;i++) { psource[i]=source[i]; } result=RandomC(psource); int len=result size();//fn組合的長度 result add((new Object[]{source[source length ]})); for(int i= ;i<len;i++) { Object[] tmp=new Object[result get(i) length+ ]; for(int j= ;j<tmp length ;j++) { tmp[j]=result get(i)[j]; } tmp[tmp length ]=source[source length ]; result add(tmp); } } return result; } static ArrayList<Object[]> cmn(Object[] source int n) { ArrayList<Object[]> result=new ArrayList<Object[]>(); if(n== ) { for(int i= ;i<source length;i++) { result add(new Object[]{source[i]}); } } else if(source length==n) { result add(source); } else { Object[] psource=new Object[source length ]; for(int i= ;i<psource length;i++) { psource[i]=source[i]; } result=cmn(psource n); ArrayList<Object[]> tmp=cmn(psource n ); for(int i= ;i<tmp size();i++) { Object[] rs=new Object[n]; for(int j= ;j<n ;j++) { rs[j]=tmp get(i)[j]; } rs[n ]=source[source length ]; result add(rs); } } return result; }
}
三 利用動態規劃的思想求排列和組合
復制代碼 代碼如下: package Acm; //強大的求組合數 public class MainApp { public static void main(String[] args) { int[] num=new int[]{ }; String str=""; //求 個數的組合個數 // count( str num ); // 求 n個數的組合個數 count ( str num); }private static void count (int i String str int[] num) { if(i==num length){ System out println(str); return; } count (i+ str num); count (i+ str+num[i]+" " num); }
private static void count(int i String str int[] num int n) { if(n== ){ System out println(str); return; } if(i==num length){ return; } count(i+ str+num[i]+" " num n ); count(i+ str num n); } }
下面是求排列
復制代碼 代碼如下: lishixin/Article/program/Java/JSP/201311/20148
⑹ 組合計算公式
組合數的計算公式為：
組合是數學的重要概念之一，它表示從 n 個不同元素中每次取出 m 個不同元素，不管其順序合成一組，稱為從 n 個元素中不重復地選取 m 個元素的一個組合。所有這樣的組合的種數稱為組合數。
n 元集合 A 中不重復地抽取 m 個元素作成的一個組合實質上是 A 的一個 m 元子集和。如果給集 A 編序成為一個序集，那麼 A 中抽取 m 個元素的一個組合對應於數段到序集 A 的一個確定的嚴格保序映射。
(6)組合演算法教程擴展閱讀
組合數的性質：
1、互補性質：即從n個不同元素中取出m個元素的組合數=從n個不同元素中取出 (n-m) 個元素的組合數；這個性質很容易理解，例如C(9,2)=C(9,7)，即從9個元素里選擇2個元素的方法與從9個元素里選擇7個元素的方法是相等的。
2、組合恆等式：若表示在 n 個物品中選取 m 個物品，則如存在下述公式：C(n,m)=C(n,n-m)=C(n-1,m-1)+C(n-1,m)。
⑺ 數學排列組合公式演算法
交你個簡單的運用發比如a3/5=5*4*3
這個你就從5開始往下乘3位數，也就是
5*4*3在看a2/5=5*4
同樣從5開始往下乘，乘兩位，
也就是5*4在比如a4/7=7*6*5*4
這就是從7開始往下乘4位，
就是7*6*5*4又如a5/7=7*6*5*4*3
這就是從7開始往下乘5個，就是7*6*5*4*3
其實這些公式很容易的，向這種，你就看a
下面的數字是多少，就從那個數開始乘，
a上面的那個數字就是它要向下乘的幾位數。
你照我上面寫的這個方法，隨便寫兩個算算就會明白的
n!那個是階層
和上面有個共同點，其實n！又可以寫成a
n/n
比如5！=a5/5
即從5開始往下乘5位，5*4*3*2*1
這種你就從那個數字開始往下成，一直乘到1
希望我的方法能讓你學會，你自己試試