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

Re: [問題] 組合編碼問題

看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間13年前 (2011/06/21 18:30)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串2/2 (看更多)

假若要在 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)