作者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