作者LPH66 ( )
看板Programming
标题Re: [问题] 从n中取k可重复的组合想不全部展开
时间Wed May 1 11:30:21 2024
※ 引述《dinohsu1019 (杰生方的铁粉)》之铭言:
: 投资组合为1将权重k等分分配到n个股票,每个股票可分配权重0(零),1/k,2/k,...1
: (全部)将k等分分配到n个股票。
: 即「从n中取k可重复的组合」,组合数为 C(n+k-1,n-1)。
: 故权重编号范围为1~C(n+k-1,n-1)
: 权重串列(整数版)为(n,0,...0,0),(n-1,1,...,0,0),...(0,0,...,0,n)。
: 权重串列(小数版) = 权重串列(整数版)/n。
: 我的目的不是要将全部组合展开,而是要随机映射编号和组合,
: 例如:n=8, k=4时有165种组合,
: 正向:当我输入编号21时要输出 (0.375, 0.375, 0.25, 0.0)
: 反向:当我输入(0.375,0.375,0.25,0.0)要得到编号21
: 有什麽方法可以计算?感谢先
: https://tinyurl.com/yvkpanm6
於是你的需求是将重覆组合以某个顺序排序後直接求出该组合是排序中第几位 (及反之)
这种组合和序数转换题型有一个通用的想法是:
将这个排序顺序做成有某种分组的样子
(例如第一权重相同的全部排在一起)
然後依照这个分组顺序数过去
每数一组直接算出分组有多少元素, 然後判断你要的第 N 组是不是在这里面
发现是了的话这个分组的特性就会变成确定的组合项目
然後就能递回往下求该组内的对应组合
使用在这个题目的话, 以你所产生的顺序来看 (先不要除以总权数)
1 号组合是最後一个权重在第一档
2~9 号组合是最後一个权重在第二档
10~45 号组合是最後一个权重在第三档
46~165 号组合是最後一个权重在第四档
这是一个大分组, 每一个分组的数量可以先放一个权重在对应的档再分余下权重
所以第一大组是权重 7 分在 1 档, 计 C(1+7-1, 1-1) = C(7,0) = 1 种
第二大组是权重 7 分在 2 档, 计 C(2+7-1, 2-1) = C(8,1) = 8 种
第三大组是权重 7 分在 3 档, 计 C(3+7-1, 3-1) = C(9,2) = 36 种
第四大组是权重 7 分在 4 档, 计 C(4+7-1, 4-1) = C(10,3) = 120 种
可以验证上面算出来的正是再上面四个大组的数量
所要的 21 号组合, 因 1+8 < 21 但 1+8+36 >= 21
故知属於第三大组的 21-1-8=12 号组合
而每个大分组中又可依据这最後一档有多少权重分中组
这 36 种组合中
第三档有权重 1 的余下权重 7 分在 2 档, 计 C(2+7-1, 2-1) = C(8,1) = 8 种
权重 2 的余下权重 6 分在 2 档, 计 C(2+6-1, 2-1) = C(7,1) = 7 种
权重 3 的余下权重 5 分在 2 档, 计 C(2+5-1, 2-1) = C(6,1) = 6 种
等等
所要的 12 号组合, 因 8 < 12 但 8+7 >= 12 故知属於第二中组, 即第三档有权重 2
其为此组 (权重 6 分在 2 档) 中的 12-8=4 号组合
-- 至此确定了第三档权重 2, 以後皆无权重, 而前面是权重 6 分 2 档的 4 号组合
这後半部份即是和原来完全相同的问题, 因此即可递回求解
这个例子中的 4 号组合是 (3,3), 所以加上第三档权重 2, 以後皆无, 即得 (3,3,2,0)
倒算也能类似的求出来: (3,3,2,0) 最後一个在第三档权重 2
所以在第三大组第二中组, 它前面两个大组有 1 和 8 组, 一个中组有 8 组, 总计 17
然後递回求出 (3,3) 的顺序 4 号组合, 所以所求是 17+4 = 21 号组合
====
话说回来, 你想要的其实是随机求一个组合
那其实各组合的顺序并不一定要是这个顺序
也可以直接用比较好分组的方式来做
例如可以直接用类似上面分中组的方式排序
这样顺序就会变成反向字典顺序:
(8,0,0,0)
(7,1,0,0) (7,0,1,0) (7,0,0,1)
(6,2,0,0) (6,1,1,0) (6,1,0,1) (6,0,2,0) (6,0,1,1) (6,0,0,2)
(5,3,0,0) (5,2,1,0) (5,2,0,1) (5,1,2,0) (5,1,1,1) (5,1,0,2)
(5,0,3,0) (5,0,2,1) (5,0,1,2) (5,0,0,3)
(4,4,0,0) ....
每一组中的组合数也能类似求得:
第一档权重 8 则余下权重 0 分 3 档, 计 C(3+0-1, 3-1) = C(2,2) = 1 种
权重 7 则余下权重 1 分 3 档, 计 C(3+1-1, 3-1) = C(3,2) = 3 种
权重 6 则余下权重 2 分 3 档, 计 C(3+2-1, 3-1) = C(4,2) = 6 种
权重 5 则余下权重 3 分 3 档, 计 C(3+3-1, 3-1) = C(5,2) = 10 种
等等
随便举个 17 号组合: 1+3+6 < 17 但 1+3+6+10 >= 17 故知属於第一档权重 5 的组
其为组内 17-1-3-6 = 7 号组合, 因此余下三档即是权重 3 分 3 档的 7 号组合
递回求出来是 (0,3,0), 所以所求组合即是 (5,0,3,0)
倒求顺序的手法类似就不在这里详述了
====
总之概念就是, 把你要的顺序拆成各个可以分别直接求出组合数的小块
这样你只要算过去就会知道你要的组合是在哪个小块里
然後小块中的哪里这问题是原问题的缩小版, 所以可以递回求解
求顺序则是倒过来, 确定组合属於哪个小块之後求出前面所有小块的组合数加总
再加上扣掉组合性质後余下的组合递回求出是这个小块中的第几个, 总合就是答案
--
Ace Snake Santa Clover Junpei June Seven Lotus 9th man cabin kitchen casino
shower operating room laboratory T H E chart captain quarter confinement
torture room steam engine room cargo chapel library study incinerator Gigantic
Q director office security N O N A R Y archives control laboratory
pec treatment garden pantry gaulem bay rec room crew quarters infirmary lounge
elevator Tenmyouji Quark Dio G A M E S Luna Phi Sigma Alice Clover K
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.10.56.178 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Programming/M.1714534223.A.73D.html
※ 编辑: LPH66 (123.194.181.180 台湾), 05/01/2024 16:09:24