[討論] 整數陣列限定總和與上下界,取亂數值

[tropical72 (藍影)]

抱歉，標題我想半天我還是不知道該怎麼說明，看完題目若知屬什麼問題，

請不吝告知，將更改為較合題意之標題，謝謝。

實際問題如下敘述

一陣列裡有 n 個整數元素，假設為 arr[n]，若對每個 arr[i] 取亂數，
每個 arr[i] 又有個自之上、下界，假設分別為 low[i] 與 up[i]，
(故 low 與 up 也是有 n 個整數元素 )，同時限定此陣列之總和剛好為 sum，
即 arr[0] + arr[1] + ...arr[n] = sum。其中 sum 保證介於

low[0] + low[1] + .... + low[n-1] 與
up[0] + up[1] + .... + up[n-1] 之間，

試問該如何決定陣列 arr 內之元素？


我嘗試的解法如下 (獻醜了)

演算法大致如下所述

process:
   assign low to arr
   slack = sum - (sum of low array)

   for i:= 1 to slack
       * cal column prob. of (range of up[j],arr[j]) (prob[j])
       * generate rnd = random(0,1)
       * find min j , st prob[j] >= rnd
       * increment arr[j]
   end for
end process

可能沒寫那麼清楚，提供小弟 website 上詳細說明

http://edisonx.pixnet.net/blog/post/81995873

website 裡我自提到，當 sum of (up[i] - low[i]) 很大時，

執行時間會拉大，但考慮了甚多問題後，乃覺得這方式最為穩定、簡易，

殊不知是否有其它解決方案？

不知各位版友對於此問，或小弟嚐試之作法有無意見，或想法可供參考，

小弟感激不盡。

--
    No matter how gifted you are,
       alone, can not change the world. 

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: tropical72      來自: 180.177.78.41        (10/20 03:39)
→ AmosYang:這個題目本身與你的解法…很難寫成 paper
→ AmosYang:但如果你能 *證明* 你的方法能產生最好的 randomness ,
→ AmosYang:這個“證明的方法”或許會有學術價值且寫成 paper
→ tropical72:謝謝 A 大建議, 其實比較想知道還能怎更快, 感謝
→ AmosYang: 求快之前要先求正確啊 XD
→ tropical72:是啊!提出的 algorithm 都有問題,還在想怎樣方式兼具有
→ tropical72:效性與正確性. XD