作者bob123 ()
看板Programming
標題Re: [問題] 排列組合，相同物品分發制不同容器
時間Sun Apr 15 06:54:33 2012
※ 引述《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
1F：推 yauhh:好Python 61.231.67.34 04/15 12:41
2F：→ lovesnake:對耶! 抱歉 我的H忘了扣掉一開始要分 140.121.216.68 04/15 14:14
3F：→ lovesnake:一個給每個容器了!! 感謝您~ 140.121.216.68 04/15 14:15
4F：→ bob123:H(3,8)-3*H(2,8)+3*H(1,8) 也是可以 但是若 111.255.31.152 04/15 19:26
5F：→ bob123:題目變形為容器數=5,6,7... 運算量的浪費會 111.255.31.152 04/15 19:29
6F：→ bob123:可能會越來越多 111.255.31.152 04/15 19:30
7F：→ bob123:y大讓我一開始嚇到還以為我在cpp版寫py XD 111.255.31.152 04/15 19:33