林宏信

小工程師,就讀五專,喜好軟體開發、音樂創作、寫作、0 A. D.,經營部落格 WANcatServer 網貓伺服器。 website: wancat.cc keybase: https://keybase.io/wancat

專案介紹:排列組合計算機

近來數學課在教排列組合,排列組合不簡單,很難考慮周全,因此我設計了一個排列組合計算機,根據設定條件窮舉出所有可能,並一一列出。

排列組合計算機

GitHub 與使用教學

我覺得這個工具對於學習排列組合蠻有幫助的,當然工具沒辦法教你排列組合,但是可以通過觀察結果來促進思考,或找到沒考慮周全的地方,以及驗證題目是否正確。

其實用電腦窮舉不難,只是排列組合的題目變化多,難以用一個程式解出所有題目,但我發現其中基本上都可以分成兩個部份:窮舉與篩選,先窮舉出所有結果,再將結果進行篩選。窮舉基本上大同小異,就是排列/組合重複/不重複,每個題目不一樣的主要是篩選的部份,因此我設計讓使用者自己在網頁上用 JavaScript 寫篩選器,這樣各種複雜的條件都能做出來,這裡是運用 JavaScript 的 eval() 函式,可以將一個字串轉成 JavaScript 語句,這感覺超不安全的,但既然不是在伺服器端,應該不會有什麼資安疑慮,程式若是失控,請使用者自行負責。

整個專案就是一個靜態網頁,託管在 GitHub Page,程式在瀏覽器端執行運算,整個專案相當簡短,全部 JavaScript 不過一百多行。由於排列組合的結果數上升得很快,我有做一個簡易的保護機制,確保總運算量不會超過十億,在這之前我多次搞到 RAM 吃光,整台電腦當機(但主因是 VSCode 和 TabNine 吃太多記憶體)。

使用上由於要寫 JavaScript,或許會有些門檻,但畢竟只是對陣列數值做加總、判斷,我在 GitHub 上有提供一些範例,應該參考一下就會寫了。這裡列出幾個範例供參考:

範例一:數字問題

題目:找出由 0~5 組成的所有三位數,且為 3 的倍數

從 6 個元素,取出 3 個項目,首項非零,以及以下篩選器:

(array) => {
    let sum = 0
    for (let value of array) sum += value
    return sum % 3 == 0
}

可得到總共有 40 個結果:102 105 120 123 132 135 150 153 201 204 210 213 231 234 240 243 312 315 321 324 342 345 351 354 402 405 420 423 432 435 450 453 501 504 510 513 531 534 540 543

範例二:舞伴問題

題目:有五對夫婦跳舞,若夫婦彼此不共舞,舞伴為一男一女組合,舞伴的配法總數

從 5 個元素,取出 5 個項目,加上以下篩選器:

(array) => {
    for (let i in array) if (array[i] == i) return false
    return true
}

可得到答案為 44 種。

如果這個工具對你有幫助,希望你幫我拍手或是到 GitHub 上給個星星!


發佈評論

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區