1. 定義:
組合數(shù):從m個(gè)不同元素中任取n(n<=m)個(gè)元素拼成一組俄删,叫做從m中取n個(gè)元素的組合延柠。能夠取的所有可能叫組合數(shù)嗤栓。公式如下:
全排列:從m個(gè)不同元素中佑刷,任取n(n<=m)個(gè)元素按照一定順序排列起來(lái)忘闻,叫做從m中取n個(gè)數(shù)的一個(gè)排列钝计。當(dāng)m=n時(shí)的所有排列情況,叫做全排列齐佳。
全排列數(shù)f(n) = n!
區(qū)別:排列可以看作是同樣情況下組合的子集葵蒂,由于需要按順序排列,因此少了一些情況重虑。
2. JAVA實(shí)現(xiàn)
-->全組合:
運(yùn)行結(jié)果:
運(yùn)行過(guò)程:
舉例3個(gè)元素:a,b,c践付。所以一共有2^3=8個(gè)結(jié)果。所以i=0,1,2,3,...,7分別對(duì)應(yīng)輸出以上結(jié)果
將i轉(zhuǎn)換為二進(jìn)制i=1=001缺厉,i=2=010永高,i=3=011
1)j=0隧土;1<<j =001與i=001相與返回1 輸出a
-->全排列:
遞歸
* 從集合中依次選出每一個(gè)元素,作為排列的第一個(gè)元素命爬,然后對(duì)剩余的元素進(jìn)行全排列曹傀,如此遞歸處理
* 從而得到所有元素的全排列。以對(duì)字符串a(chǎn)bc進(jìn)行全排列為例饲宛,我們可以這么做:以abc為例:
* 固定a皆愉,求后面bc的排列:abc,acb艇抠,求好后幕庐,a和b交換,得到bac
* 固定b家淤,求后面ac的排列:bac异剥,bca,求好后絮重,c放到第一位置冤寿,得到cba
* 固定c,求后面ba的排列:cba青伤,cab督怜。
** 即遞歸樹(shù):
str: a b c
ab ac ba bc ca cb
result: ?abc acb ?bac bca ? ?? cab cba
運(yùn)行結(jié)果: