Re: [討論] 整數陣列限定總和與上下界,取亂數值
看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間13年前 (2011/10/21 09:29)推噓8(8推 0噓 6→)留言14則, 2人參與討論串4/4 (看更多)
我覺得要先考慮你的機率分部，如果你的目的是如 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
推
10/21 09:40, , 1F
10/21 09:40, 1F
→
10/21 09:41, , 2F
10/21 09:41, 2F
→
10/21 09:42, , 3F
10/21 09:42, 3F
→
10/21 09:42, , 4F
10/21 09:42, 4F
推
10/22 19:40, , 5F
10/22 19:40, 5F
→
10/22 19:40, , 6F
10/22 19:40, 6F
推
10/22 20:43, , 7F
10/22 20:43, 7F
推
10/25 00:16, , 8F
10/25 00:16, 8F
→
10/25 00:16, , 9F
10/25 00:16, 9F
推
10/26 08:42, , 10F
10/26 08:42, 10F
推
10/26 08:44, , 11F
10/26 08:44, 11F
→
10/26 08:45, , 12F
10/26 08:45, 12F
推
10/26 21:53, , 13F
10/26 21:53, 13F
推
10/27 07:57, , 14F
10/27 07:57, 14F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12