作者tropical72 (藍影)
站內Prob_Solve
標題[問題] 組合編碼問題
時間Tue Jun 21 17:56:15 2011
數學沒很好，希望可以給一點意見。
先假設有 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
1F：→ suhorng:可以的, 但是計算過程會需要計算 mCn 之類... 如果 mCn 本 06/21 18:02
2F：→ suhorng:身就很大(超過long long之類,或算起來很慢)可能也不太方便 06/21 18:02
3F：→ suhorng:如果現在要對在 m 個數中取 n 個的組合進行編號, 那麼以 06/21 18:06
4F：→ suhorng:(由小到大)第 k 個數字開頭的組合 編號自然在 06/21 18:06
5F：→ suhorng:C(n-1,m-1)+C(n-2,m-1)+...+C(n-k,m-1)和 06/21 18:12
6F：→ suhorng: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
7F：→ suhorng:所以在編解的時候可以一一枚舉該位數字,順便計算編號 06/21 18:13
8F：→ suhorng:有點類似康托展開,但是這次子問題的大小不是定值 06/21 18:14
9F：→ suhorng: ^^^^^^^^^^^打錯了 多一項 06/21 18:15
抱歉一直插隊, 現在補齊！該數學式確實沒見過, 康托展開我也再去查查,
該數學式應是 (組合)--->(編號)，至此應可解決我的問題.
另一疑問是，是否有另一組類似 (編號)----> (組合)
※ 編輯: tropical72 來自: 180.177.73.222 (06/21 18:28)
10F：→ suhorng:反過來從編號求出組合也是一樣的方法,就看編號位在哪一段 06/21 18:32
11F：→ suhorng:就知道現在應該要取剩下的第幾大的數字 06/21 18:32