非统一概率随机
copied from
http://forum.xda-developers.com/showthread.php?t=856735
namespace RandomWeighting{ class Program { static void Main(string[] args) { char[] Select = new char[10] {'A','B','C','D','E','F','G','H','I','J'}; int[] Weight = new int[10] {10,30,25,60,20,70,10,80,20,30}; int[] WeightSum = new int[10]; int i,j,k; Random Rnd = new Random(); WeightSum[0]=Weight[0]; for (i = 1; i < 10; i++) WeightSum[i] = WeightSum[i - 1] + Weight[i]; for (j = 0; j < 70; j++) { k = Rnd.Next(WeightSum[9]); for (i = 0; k > WeightSum[i]; i++) ; Console.Write(Select[i]); } Console.WriteLine(); } }} ?
The most common thought of choose with probability is make the elements to be as many as their probability is.
And then uniformly choose some one from the new range,that will be the answer.
a1 ??3 ???-> p1 = 3 / (3 + 6) = ?
a2 ??6 ???-> p2 = 6 / (3 + 6) = ?
if a1 and a2 are of equality probability then make the position 0 denote a1 and position 1 for a2.
0 ???1
a1 ?a2
use Random will uniformly choose one of them.
Now things got changed.We enlarge the amount of elements by some number ,say 9
0???????? 1???????????? 2??????? 3?? ? ? ? 4? ? ?? ? 5 ? ? ? ? 6 ?? ? ? ? 7 ? ? ? ? ? 8 ?? ? ? ? ? 9
|<----------- ?a1 --------->|<-------------------------- a2 ----------------------->|
(ATTENTION:
The length of a1 is 3 now , and the length of a2 is 6.
It’s the length,not the numbers contained in their ranges.)
(Suppose rand() returns both the low bound and upper bound)
if Random.rand() * 9 ?returns number less or equals than 3, we will choose a1,
else choose a2.
a1’s length could be calculated through 9 * p1 = 3;
a2’s length could be calculated through 9 * p2 = 6;
But the number 3 is the key for choosing. Considering there’s one more element a3. when should a3 be chosen? If random number greater than 9, a3 will be chosen.(Also the random number is calculated through Random.rand() * N, where N equals to a1 + a2 + a3.)
So the separators are
N * p1 , N * p1 + N * p2
More generally. there will be more elements like listed below:
S1 = N * p1
S2 = N * p1 + N * p2
S3 = N * p1 + N * p2 + N * p3
S4 = N * p1 + N * p2 + N * p3 + N * p4
…....
Sn = N * p1 + N * p2 + N * p3 + … + N * pn
R ?= Random.rand() * N;
So ,the solution will be described as this:
Start from s1, ?if some Si is greater than R.then the i th element is chosen.
We also noticed both Si and R are composed of N,so N could be discard on calculating.
Si = Sigma pi ?????
Here, we would discover that the Si is the accumulative probability of discrete elements.
Maybe this can also be used in the continuous situation.