作者ssd860505da (JAGER)
看板Python
標題[問題] 分堆問題
時間Sun Aug 21 00:50:50 2016
大家好，我是新手^^
最近練習寫程式時，常常寫到一半就發現原來這有內建模組OAO!
雖然很像在做白工，不過過程中也學習到了不少
我寫了一個排列組合的分堆問題，
就是將n個物體分成m組
也就是....
A1+A2+A3+....+Am=n的非負整數解(排組的H運算)
我想知道這有沒有內建的function =v=?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.57.196
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1471711853.A.9CD.html
1F：推 Sunal: 整數分割？ 08/21 02:45
2F：→ bigpigbigpig: 內建：沒有。先想想m個0和(n-1)個1有幾種不同的排列 08/21 08:44
3F：→ bigpigbigpig: 更正：n個0和(m-1)個1 08/21 08:45
我有想過那種方法，可是itertools.permutations是對於no_repeat作排列
直接用再把一樣的情況去掉的話會有MemoryError
我不知道有沒有對於有重複element的permutations
所以我的方法是...
[ n , 0 , 0 , 0 ,....., 0](m-1個0)
[n-1, 1 , 0 , 0 ,....., 0]
[n-1, 0 , 1 , 0 ,....., 0]
......
[n-1, 0 , 0 , 0 ,....., 1]
[n-2, 2 , 0 , 0 ,....., 0]
[n-2, 1 , 1 , 0 ,....., 0]
以此類推，直到
[0 , 0 , 0 , 0 ,....., n]結束
※ 編輯: ssd860505da (220.136.57.196), 08/21/2016 10:59:34
※ 編輯: ssd860505da (220.136.57.196), 08/21/2016 11:00:47
4F：→ bigpigbigpig: 方向正確，m,n不大的話，可用set來篩選不重複的排列 08/21 11:16
5F：→ bigpigbigpig: 有效率的解決方法看下面這篇： 08/21 11:32