PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 組合編碼問題

看板Prob_Solve (計算數學 Problem Solving)作者 (藍影)時間13年前 (2011/06/21 17:56), 編輯推噓0(0推 0噓 11→)
留言11則, 1人參與, 最新討論串1/2 (看更多)
數學沒很好，希望可以給一點意見。 先假設有 5 個數要取 3 數做組合，共 5C3 = 10 種， 並「依序」做輸出的話長這樣 (1) 1 2 3 (2) 1 2 4 (3) 1 2 5 (4) 1 3 4 (5) 1 3 5 (6) 1 4 5 (7) 2 3 4 (8) 2 3 5 (9) 2 4 5 (10) 3 4 5 現我想要對它們做編碼動作，若以編號 0 為第一組， 編號 0 : 1 2 3 編號 4 : 1 3 5 請問這樣，有沒有辦法做 encode(組合對到編號) / decode(編號對到組合) 動作？ 由於實際問題 mCn 結果還蠻大的，但我只需紀錄其「該組合出現次數」即可， 所以想用這種方式節省記憶體空間，無奈便是 編解碼 那裡不知該如何下手， 請各位有經驗之版友予以意見， 謝謝各位不吝指教。 -- YouLoveMe() ? LetItBe() : LetMeFree(); -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.73.222
→
06/21 18:02, , 1F
可以的, 但是計算過程會需要計算 mCn 之類... 如果 mCn 本
06/21 18:02, 1F
→
06/21 18:02, , 2F
身就很大(超過long long之類,或算起來很慢)可能也不太方便
06/21 18:02, 2F
→
06/21 18:06, , 3F
如果現在要對在 m 個數中取 n 個的組合進行編號, 那麼以
06/21 18:06, 3F
→
06/21 18:06, , 4F
(由小到大)第 k 個數字開頭的組合 編號自然在
06/21 18:06, 4F
→
06/21 18:12, , 5F
C(n-1,m-1)+C(n-2,m-1)+...+C(n-k,m-1)和
06/21 18:12, 5F
→
06/21 18:12, , 6F
C(n-1,m-1)+C(n-2,m-1)+...+C(n-k,m-1)+C(n-k+1,m-1)-1間,
06/21 18:12, 6F
→
06/21 18:13, , 7F
所以在編解的時候可以一一枚舉該位數字,順便計算編號
06/21 18:13, 7F
→
06/21 18:14, , 8F
有點類似康托展開,但是這次子問題的大小不是定值
06/21 18:14, 8F
→
06/21 18:15, , 9F
^^^^^^^^^^^打錯了 多一項
06/21 18:15, 9F
抱歉一直插隊, 現在補齊！該數學式確實沒見過, 康托展開我也再去查查, 該數學式應是 (組合)--->(編號)，至此應可解決我的問題. 另一疑問是，是否有另一組類似 (編號)----> (組合) ※ 編輯: tropical72 來自: 180.177.73.222 (06/21 18:28)
→
06/21 18:32, , 10F
反過來從編號求出組合也是一樣的方法,就看編號位在哪一段
06/21 18:32, 10F
→
06/21 18:32, , 11F
就知道現在應該要取剩下的第幾大的數字
06/21 18:32, 11F
‣ 更多 tropical72 的文章
文章代碼(AID): #1E06h4Uk (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 tropical72 的文章
文章代碼(AID): #1E06h4Uk (Prob_Solve)