作者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/cn.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