[問題] 組合編碼問題

[tropical72 (藍影)]

數學沒很好，希望可以給一點意見。

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