iT邦幫忙

DAY 2
3

用Javascript征服演算法系列 第 2

用Javascript征服演算法 (1-排列組合)

挑選一個排列組合的題目,希望各位看完可以稍稍理解排列組合的題目該如何去解析適合用程式碼實作的解法
在演算法中,排列組合算是相對容易的一個常見問題,因此我們第一個題目就先從排列組合來下手吧!

題目如下:
請寫出一個程式,用旋轉順序(Ratition Order)來列出n個元素的所有排列(在此不考慮可以重複集合內元素)

探討方式:
我習慣在看到一個題目時,想辦法從一些現象去觀察出規律,一但有了規律就很方便可以程式化
因此,先從簡單的{1,2}的排列組合來看的話,這集合的排列組合總共就是兩組,便是以下所列

{1,2},{2,1}

由這邊稍微可以看出兩個數字對調後可產出新的組合的特性,接下來再來觀察3個數字的排列組合{1,2,3}
首先我先套用兩個數字做對調的方式來產生新的排列組合,因此我從{1,2,3}這個順序來做對調產生新組合

{(1),(2),3} => {2,1,3} 
=> {1,(2),(3)} => {1,3,2}
=> {(1),2,(3)} => {3,1,2}

由以上例子再繼續對新的組合作兩兩對調,就可以找到所有組合(一共六組)

{1,2,3} {2,1,3} {1,3,2} {3,2,1} {2,3,1} {3,1,2}

但如果用上述的方式,你會發現操作時需要去剔除"重複找到"的組合,這表示在程式中還需要去"比對"已經找到過的組合,而這件事情是非常浪費程式碼執行的時間的,等於你必須至少在做1次以上的次的比對,因此我們必須再去想一個可以避免找到重複組合的方式

經過幾次的嘗試跟試驗,對於"不重複數字"這個概念來下手的話,如果我們都先固定組合的第一個數字,而後剩下的數字去做對調(recursive)的動作,就可以直接找到所有組合,以下為示範

{1,2,3} 固定1然後對2,3做對調會找到 {1,3,2} 接著將{1,2,3}的2與1做旋轉後得到{2,1,3} 固定2然後對1,3做對調會找到 {2,3,1} 接著將{1,2,3}的1,3做旋轉後得到
{3,2,1} 固定3然後對2,1做對調會找到 {3,1,2}

至此就找到共六組的所有排列組合,接著重新檢視我們使用的方式是否有規律性,不管集合內的數字n多大,我們都可以用上述方法先固定第一個數字的方法,接著對剩下數字做遞迴運算即可

其實從數學角度來說,集合裡面有三個數字,而又不重複數字的原則,可以透過階層算法來知道所有組合就是
3! = 3*2*1 = 6

但要如何去解釋為何是n(n-1)(n-2)? (習慣去理解解法而不是死背XD)

可以先從我們的解法 =>>"固定某一個數字" 來想,假設我們集合中有n個數字,所以我先固定第一個數字後,代表剩下會有(n-1)個數字作遞迴來產生新組合,而對於(n-1)個數字的組合來說,也需要固定(n-1)個數字後,去遞迴(n-2)個剩下的數字來產生新組合,如此不斷下去,直到集合中只剩下1個數字,以上這段話來舉例說明的話

{1,2,3,4} 先固定第一個數字 ==>[1,{2,3,4}] 剩下(4-1)個數字去作遞迴,那{2,3,4}如何去找出所有組合,也是同樣的規則,固定第一個數字 [2,{3,4}] 此時就剩下(4-2)個數字作遞迴, 以此類推最後就剩下1個數字去作遞迴,因此從上述要如何去計算所有組合,可以想見,固定完第一個數字後,會需要再轉換固定第二個數字,因此可以想成第一層是由4個數字輪流去固定來對剩下的集合遞迴,而第二層遞迴是由3個數字去輪流固定來對剩下的集合作遞迴,而第三層是由2個數字作固定來遞迴剩下集合,最後剩下1數字就不需要做固定遞迴,因此就可以得到下列的算是

4*3*2*1 = 4 * (4-1) * (4-2) * (4-3) <n(n-1)(n-2)......1>

以上就是針對這題目的分析,不知道大家有沒有懂QQ,其他類似的排列組合問題也是可以透過上述的觀察方式去找到規律來得到解法,希望這篇可以對於排列組合的題目有拋磚引玉的效果QQ

有任何不清楚的地方再麻煩各位在下方留言,謝謝謝謝

ps.此題目應該在javascript應用上還算常見,可能會需要對n個不同選擇作出所有排列 ex: 自動排列出四種選項的喜好順序給使用者選取

下一篇就會針對此解法去介紹如何作出Javascript版本囉~灑花


上一篇
用Javascript征服演算法 (序)
下一篇
用Javascript征服演算法 (1-排列組合-Javascript實作)
系列文
用Javascript征服演算法10

2 則留言

0
葉宇霖
iT邦新手 4 級 ‧ 2013-09-24 17:34:30

謝謝使耽溺 喚醒我沉睡已久的數學魂
愛你愛你

GOGO math~

0
fillano
iT邦超人 1 級 ‧ 2013-09-24 18:48:46

讚喜歡 這個推導過程才是精華阿!!!

真的~你懂我><開心

我要留言

立即登入留言