作者tropical72 (藍影)
站內Prob_Solve
標題Re: [討論] 整數陣列限定總和與上下界,取亂數值
時間Fri Oct 21 02:16:29 2011
謝謝您的提醒，的確是我的誤失，若將演算法改如下請問如何？
改善方法一 : 去掉累計機率概念，新增 集合洗牌 概念
N = 3 , sum = 4
[0] [1] [2]
low 0 0 0
high 1 5 7
1. 初始化 arr = low = {0,0,0}
計算 slack = sum - (sum of arr) = 4 - 0 = 4
2. rng[i] = high[i] - arr[i]
rng = {1,5,7}, rng 為非 0 元素之 index 加入集合 SET 中,
此例為 SET = {0,1,2}
3. 對 SET 做 shuffle , 取出第一個元素出來, 假設取出為 k
遞增 arr[k]。
4. 回到 step 2, 執行 slack 次
改善方法二 : 改善累計機率概念 ， 加入集合
N = 3 , sum = 4
[0] [1] [2]
low 0 0 0
high 1 5 7
1. 初始化 arr = low = {0,0,0}
計算 slack = sum - (sum of arr) = 4 - 0 = 4
2. rng[i] = high[i] - arr[i]
rng = {1,5,7}, rng 為非 0 元素之 index 加入集合 SET 中,
此例為 SET = {0,1,2}，
3. 再對 SET 做累計機率統計，因裡面有 3 個元素，均勻分配下，
prob[0] = 0.3333 , prob[1] = 0.6666 , prob[2] = 1.0
4. 取一隨機亂數 rnd = (0,1] ， find min k st rnd <= prob[k]
假設 rnd = 0.05 , k = 1, 再遞增 arr[ SET[k] ]
5. 回到 step 2, 執行 slack 次
請示
請示乍看下，上二種法是否算是均勻？
改善 1 用到多次之洗牌法 效率從原本的 O(n) 又變到了 O(n^2)，
改善 2 若無問題的話，暫時應以此方案做為解決，
更好之解法乃待尋便是 (目前似乎沒什麼人在探討這問題 XD)
最後謝謝您不吝指正，非常感激 *^_^*
※ 引述《tkcn (小安)》之銘言：
: 我認為你的解法沒辦法產生真的隨機，
: (也可能是我們對題目的定義不同))
: 下面是個例子:
: N = 2, sum = 1
: [0] [1]
: low: 0 0
: high: 2 10
: 也就是必須滿足:
: 0 <= arr[0] < 2
: 0 <= arr[1] < 10
: arr[0] + arr[1] = 1
: 能夠滿足上述條件的解有兩組:
: 1. {0, 1}
: 2. {1, 0}
: 在我的觀點看來，這兩組解出現的機率必須是相同，才是正確的隨機。
: 但我認為你提出的程式，出現 {0, 1} 這組解的機會較高。
: : http://edisonx.pixnet.net/blog/post/81995873
--
No matter how gifted you are,
alone, can not change the world.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
※ 編輯: tropical72 來自: 180.177.78.41 (10/21 02:30)
1F：推 LPH66:其實法一不用多次洗牌 只要隨機取出一個 SET 裡的元素即可 10/21 03:07
2F：→ LPH66:配合 heap 的 decrease_key 有可能降到 nlogn... 10/21 03:07
3F：→ tropical72:!! 我竟又複雜化了，謝謝 LPH66 提點，感激不盡。 10/21 03:44