作者suhorng ( )
站內Prob_Solve
標題Re: [問題] 組合編碼問題
時間Tue Jun 21 18:30:45 2011
假若要在 1, 2, 3, 4, 5 間選三個 編號
0 1 2 3 \
1 1 2 4 | 4
2 1 2 5 | C = 6
3 1 3 4 | 2
4 1 3 5 |
5 1 4 5 /
6+0 2 3 4 \ 3
6+1 2 3 5 | C = 3
6+2 2 4 5 / 2
2
6+3+0 3 4 5 | C = 1
2
大概是類似這種感覺, 跟我們對 n! 編號時類似, 但子集合的大小不再是固定的
//推文有些打錯 抱歉
Encode (U,seq,len) // seq[0...len-1] 是待編碼的組合(陣列)
if len = 1 then return 0
ret ← 0
kth ← 求出 seq[0] 是 U 由小到大第幾大的數字 (1≦kth≦|U|)
for i = 1...kth-1
|U|-i
ret ← ret + C
len-1
return ret + Encode(U\{seq[0]}, seq+1, len-1)
n n-1 n-2 m n+1
而 C + C + C + ... + C = C
m m m m m+1
n n-1 n-2 n-k n+1 k
所以 C + C + C + ... + C = C - C
m m m m m m
//其實也不用這麼迂迴...從第 k 大的數字往後數, 數量自然是 C(k,m) 個
※引述《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 結果還蠻大的，但我只需紀錄其「該組合出現次數」即可，
: 所以想用這種方式節省記憶體空間，無奈便是 編解碼 那裡不知該如何下手，
: 請各位有經驗之版友予以意見，
: 謝謝各位不吝指教。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.147.134
※ 編輯: suhorng 來自: 59.115.147.134 (06/21 18:34)
1F：推 tropical72:神之手出手相助了!! 大推 !! 非常感謝 !! 06/21 18:41
※ 編輯: suhorng 來自: 59.115.147.134 (06/21 18:44)
2F：→ firejox:推su大大 06/21 20:39