作者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