作者stimim (qqaa)
看板Prob_Solve
标题Re: [讨论] 整数阵列限定总和与上下界,取乱数值
时间Fri Oct 21 09:29:18 2011
我觉得要先考虑你的机率分部，如果你的目的是如 tkcn 所说的，
每一个(合法的)组合出现的机率要一样，那你新的演算法还是会有问题
考虑这个例子：
N = 2, sum = 3
[0] [1]
low 0 0
high 2 10
arr[0] + arr[1] == 3
0 <= arr[0] <= 2
0 <= arr[1] <= 10
合法的解有：
{0, 3}
{1, 2}
{2, 1}
{1, 0} (1 10) 0.5
{2, 0} (0 10) 0.25
{2, 1} 0.25
{1, 1} (1 9) 0.25
{2, 1} 0.125
{1, 2} 0.125
{0, 1} (2 9) 0.5
{1, 1} (1 9) 0.25
{2, 1} 0.125
{1, 2} 0.125
{0, 2} (2 8) 0.25
{1, 2} 0.125
{0, 3} 0.125
P({2, 1}) = 0.25 + 0.125 + 0.125 = 0.5
P({1, 2}) = 0.375
P({0, 3}) = 0.125
可以看到 P({2, 1}), P({1, 2}), P({0, 3}) 都不相同
目前想到可以保证
P({2, 1}) == P({1, 2}) == P({0, 3})
的方法大概是先算出总排列数，再设法产生第 i 个排列。
不过要先把排列组合的公式算出来。
以这个例子来说，排列数很好算：
排例数 = H^3_2 - H^0_1 = 3
(用 latex 的 syntax)
randomly choose from [1 2 3] = k
generate a permutation by k
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 60.250.111.124
1F：推 tropical72:先谢谢您的回答,但此问题便是麻烦在不适以排列举出, 10/21 09:40
2F：→ tropical72:因实际上各维变数之 range 差异度难抓摸,当 range 大时 10/21 09:41
3F：→ tropical72:便耗过多时间. 但非常感谢您提供之意见与算法,这部份我 10/21 09:42
4F：→ tropical72:再细思, 感谢!! *^_^* 10/21 09:42
5F：推 FRAXIS:如果很难列举 你可以考虑用MCMC 10/22 19:40
6F：→ FRAXIS:这方法可以保证 近似於你想要的分布 10/22 19:40
7F：推 tropical72:感谢楼上提供之keyword!! 10/22 20:43
8F：推 tropical72:不好意思,我突然想问 MCMC 的话该如何做?我查了资料实 10/25 00:16
9F：→ tropical72:在不知该如何下手,不知是否有适合之说明等之类 ? 感谢. 10/25 00:16
10F：推 FRAXIS:应该是先随便造一个阵列 然後随机的改变它 10/26 08:42
11F：推 FRAXIS:像是每一步 随机挑一个i 把a[i]+1(or -1) 10/26 08:44
12F：→ FRAXIS:然後随机挑一个j a[j]-1(or +1) 之类的.. 10/26 08:45
13F：推 tropical72:这不就变成原演算法的步骤了吗? 还是我误会了 ? 10/26 21:53
14F：推 FRAXIS:应该是跟原来的差很多吧.. 10/27 07:57