作者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
推 tropical72:先謝謝您的回答,但此問題便是麻煩在不適以排列舉出, 10/21 09:40
→ tropical72:因實際上各維變數之 range 差異度難抓摸,當 range 大時 10/21 09:41
→ tropical72:便耗過多時間. 但非常感謝您提供之意見與算法,這部份我 10/21 09:42
→ tropical72:再細思, 感謝!! *^_^* 10/21 09:42
推 FRAXIS:如果很難列舉 你可以考慮用MCMC 10/22 19:40
→ FRAXIS:這方法可以保證 近似於你想要的分佈 10/22 19:40
推 tropical72:感謝樓上提供之keyword!! 10/22 20:43
推 tropical72:不好意思,我突然想問 MCMC 的話該如何做?我查了資料實 10/25 00:16
→ tropical72:在不知該如何下手,不知是否有適合之說明等之類 ? 感謝. 10/25 00:16
推 FRAXIS:應該是先隨便造一個陣列 然後隨機的改變它 10/26 08:42
推 FRAXIS:像是每一步 隨機挑一個i 把a[i]+1(or -1) 10/26 08:44
→ FRAXIS:然後隨機挑一個j a[j]-1(or +1) 之類的.. 10/26 08:45
推 tropical72:這不就變成原演算法的步驟了嗎? 還是我誤會了 ? 10/26 21:53
推 FRAXIS:應該是跟原來的差很多吧.. 10/27 07:57