Re: [問題] 排列組合，相同物品分發制不同容器
※ 引述《lovesnake (【忠犬攻一枚】)》之銘言：
: 求標題之演算法
: 其實就是分堆啦
: 假設有五個東西，分成三堆有幾種分法這樣
: 1 1 3
: 1 2 2
: 2 1 2
: 2 2 1
: 1 3 1
: 3 1 1
: 沒有按照順序，不過需要列印出來的大概像這樣。
: 因為是分到不同容器所以會有差別，所以內部是個SET而不是序列。相同的不能刪。
: 謝謝!!
: 已經想過很多方法，不過最終只做到東西的數量<堆數*2的時候才能成功。
: 大於的演算法始終想不出來。
問題為不同容器,相同物品 的 排列組合
課本標準解法(這邊以物品數=8,3個不同容器來舉例)
8個相同物品 █ █ █ █ █ █ █ █ █
2個分格線 | |
以兩個分隔線把一堆一樣的東西切為3分
所以這題先排分隔線的位置,再算容器內物品數
此問題的解應為C(m-1,n-1) m=物品數 n=容器數
用python寫:
from itertools import combinations
from numpy import diff
m,n = 8,3
# (0,bound1, bound2, ..., bound(n-1), m)
c = [ (0,)+i+(m,) for i in combinations(range(1,m),n-1)]
result = map(lambda x: tuple(diff(x)),c)
print result
output:
[(1, 1, 6), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (1, 6, 1), (2, 1, 5),
(2, 2, 4), (2, 3, 3), (2, 4, 2), (2, 5, 1), (3, 1, 4), (3, 2, 3), (3, 3, 2),
(3, 4, 1), (4, 1, 3), (4, 2, 2), (4, 3, 1), (5, 1, 2), (5, 2, 1), (6, 1, 1)]
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.26.21
推
04/15 12:41, , 1F
04/15 12:41, 1F
→
04/15 14:14, , 2F
04/15 14:14, 2F
→
04/15 14:15, , 3F
04/15 14:15, 3F
→
04/15 19:26, , 4F
04/15 19:26, 4F
→
04/15 19:29, , 5F
04/15 19:29, 5F
→
04/15 19:30, , 6F
04/15 19:30, 6F
→
04/15 19:33, , 7F
04/15 19:33, 7F
討論串 (同標題文章)