[問題] 分堆問題

[ssd860505da (JAGER)]

大家好，我是新手^^
最近練習寫程式時，常常寫到一半就發現原來這有內建模組OAO!
雖然很像在做白工，不過過程中也學習到了不少
我寫了一個排列組合的分堆問題，
就是將n個物體分成m組
也就是....
A1+A2+A3+....+Am=n的非負整數解(排組的H運算)
我想知道這有沒有內建的function =v=?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.57.196
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1471711853.A.9CD.html
推 Sunal: 整數分割？
→ bigpigbigpig: 內建：沒有。先想想m個0和(n-1)個1有幾種不同的排列
→ bigpigbigpig: 更正：n個0和(m-1)個1
我有想過那種方法，可是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
→ bigpigbigpig: 方向正確，m,n不大的話，可用set來篩選不重複的排列
→ bigpigbigpig: 有效率的解決方法看下面這篇：
→ bigpigbigpig: http://marknelson.us/2002/03/01/next-permutation
→ alibuda174: 這樣有符合題意嗎 http://pastebin.com/qvjx0Vqq