Re: [問題] 從n中取k可重複的組合想不全部展開

看板Programming作者LPH66 ( )時間2周前 (2024/05/01 11:30)推噓0(0推 0噓 0→)

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

※ 引述《dinohsu1019 (傑生方的鐵粉)》之銘言： : 投資組合為1將權重k等分分配到n個股票，每個股票可分配權重0(零),1/k,2/k,...1 : (全部)將k等分分配到n個股票。 : 即「從n中取k可重複的組合」，組合數為 C(n+k-1,n-1)。 : 故權重編號範圍為1~C(n+k-1,n-1) : 權重串列(整數版)為(n,0,...0,0),(n-1,1,...,0,0),...(0,0,...,0,n)。 : 權重串列(小數版) = 權重串列(整數版)/n。 : 我的目的不是要將全部組合展開，而是要隨機映射編號和組合， : 例如：n=8, k=4時有165種組合， : 正向：當我輸入編號21時要輸出 (0.375, 0.375, 0.25, 0.0) : 反向：當我輸入(0.375,0.375,0.25,0.0)要得到編號21 : 有什麼方法可以計算？感謝先 : https://tinyurl.com/yvkpanm6 於是你的需求是將重覆組合以某個順序排序後直接求出該組合是排序中第幾位 (及反之) 這種組合和序數轉換題型有一個通用的想法是: 將這個排序順序做成有某種分組的樣子 (例如第一權重相同的全部排在一起) 然後依照這個分組順序數過去每數一組直接算出分組有多少元素, 然後判斷你要的第 N 組是不是在這裡面發現是了的話這個分組的特性就會變成確定的組合項目然後就能遞迴往下求該組內的對應組合使用在這個題目的話, 以你所產生的順序來看 (先不要除以總權數) 1 號組合是最後一個權重在第一檔 2~9 號組合是最後一個權重在第二檔 10~45 號組合是最後一個權重在第三檔 46~165 號組合是最後一個權重在第四檔這是一個大分組, 每一個分組的數量可以先放一個權重在對應的檔再分餘下權重所以第一大組是權重 7 分在 1 檔, 計 C(1+7-1, 1-1) = C(7,0) = 1 種第二大組是權重 7 分在 2 檔, 計 C(2+7-1, 2-1) = C(8,1) = 8 種第三大組是權重 7 分在 3 檔, 計 C(3+7-1, 3-1) = C(9,2) = 36 種第四大組是權重 7 分在 4 檔, 計 C(4+7-1, 4-1) = C(10,3) = 120 種可以驗證上面算出來的正是再上面四個大組的數量所要的 21 號組合, 因 1+8 < 21 但 1+8+36 >= 21 故知屬於第三大組的 21-1-8=12 號組合而每個大分組中又可依據這最後一檔有多少權重分中組這 36 種組合中第三檔有權重 1 的餘下權重 7 分在 2 檔, 計 C(2+7-1, 2-1) = C(8,1) = 8 種權重 2 的餘下權重 6 分在 2 檔, 計 C(2+6-1, 2-1) = C(7,1) = 7 種權重 3 的餘下權重 5 分在 2 檔, 計 C(2+5-1, 2-1) = C(6,1) = 6 種等等所要的 12 號組合, 因 8 < 12 但 8+7 >= 12 故知屬於第二中組, 即第三檔有權重 2 其為此組 (權重 6 分在 2 檔) 中的 12-8=4 號組合 -- 至此確定了第三檔權重 2, 以後皆無權重, 而前面是權重 6 分 2 檔的 4 號組合這後半部份即是和原來完全相同的問題, 因此即可遞迴求解這個例子中的 4 號組合是 (3,3), 所以加上第三檔權重 2, 以後皆無, 即得 (3,3,2,0) 倒算也能類似的求出來: (3,3,2,0) 最後一個在第三檔權重 2 所以在第三大組第二中組, 它前面兩個大組有 1 和 8 組, 一個中組有 8 組, 總計 17 然後遞迴求出 (3,3) 的順序 4 號組合, 所以所求是 17+4 = 21 號組合 ==== 話說回來, 你想要的其實是隨機求一個組合那其實各組合的順序並不一定要是這個順序也可以直接用比較好分組的方式來做例如可以直接用類似上面分中組的方式排序這樣順序就會變成反向字典順序: (8,0,0,0) (7,1,0,0) (7,0,1,0) (7,0,0,1) (6,2,0,0) (6,1,1,0) (6,1,0,1) (6,0,2,0) (6,0,1,1) (6,0,0,2) (5,3,0,0) (5,2,1,0) (5,2,0,1) (5,1,2,0) (5,1,1,1) (5,1,0,2) (5,0,3,0) (5,0,2,1) (5,0,1,2) (5,0,0,3) (4,4,0,0) .... 每一組中的組合數也能類似求得: 第一檔權重 8 則餘下權重 0 分 3 檔, 計 C(3+0-1, 3-1) = C(2,2) = 1 種權重 7 則餘下權重 1 分 3 檔, 計 C(3+1-1, 3-1) = C(3,2) = 3 種權重 6 則餘下權重 2 分 3 檔, 計 C(3+2-1, 3-1) = C(4,2) = 6 種權重 5 則餘下權重 3 分 3 檔, 計 C(3+3-1, 3-1) = C(5,2) = 10 種等等隨便舉個 17 號組合: 1+3+6 < 17 但 1+3+6+10 >= 17 故知屬於第一檔權重 5 的組其為組內 17-1-3-6 = 7 號組合, 因此餘下三檔即是權重 3 分 3 檔的 7 號組合遞迴求出來是 (0,3,0), 所以所求組合即是 (5,0,3,0) 倒求順序的手法類似就不在這裡詳述了 ==== 總之概念就是, 把你要的順序拆成各個可以分別直接求出組合數的小塊這樣你只要算過去就會知道你要的組合是在哪個小塊裡然後小塊中的哪裡這問題是原問題的縮小版, 所以可以遞迴求解求順序則是倒過來, 確定組合屬於哪個小塊之後求出前面所有小塊的組合數加總再加上扣掉組合性質後餘下的組合遞迴求出是這個小塊中的第幾個, 總合就是答案 -- Ace Snake Santa Clover Junpei June Seven Lotus 9th man cabin kitchen casino shower operating room laboratory ＴＨＥ chart captain quarter confinement torture room steam engine room cargo chapel library study incinerator Gigantic Q director office security ＮＯＮＡＲＹ archives control laboratory pec treatment garden pantry gaulem bay rec room crew quarters infirmary lounge elevator Tenmyouji Quark Dio ＧＡＭＥＳ Luna Phi Sigma Alice Clover K -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.56.178 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1714534223.A.73D.html ※ 編輯: LPH66 (123.194.181.180 臺灣), 05/01/2024 16:09:24