Java random number with high probability

I have an array char[] Select = {'A','B','C','D','E','F','G','H','I','J'} and each element in this array has different probability to be selected. For example,

int[] Weight =  {10,30,25,60,20,70,10,80,20,30};

My requirement is to select 5 elements from this array and the element with high weight values has higher probability to be selected and these 5 elements should be different.

My plan is first sum the weight

int[] weightSum = {10, 40, 65, 125, 145, 215, 225, 305, 325, 355}

Then I use Random to generate a random number k in the range of [0,355]. Then looking for the first element which is bigger than k in the weightSum[]. This process are repeated 5 times.

The problem is that the element with high probability could be selected multiple times. I开发者_运维问答 try to remove the duplicate elements at each iteration. The duplicates are removed, but element with high weight values are not selected.

How to solve this problem?

thanks.

Not sure I understand correctly, but how about something like this:

• after first selection you remove the selected element from char[] Select
• you also remove the corresponding weight from int[] Weight
• regenerate int[] weightSum
• repeat the whole process

don't maintain the cumulative sum or adjust it each time: (requires O(n) for each selection though)

char[] Select = {'A','B','C','D','E','F','G','H','I','J'};
int[] Weight = {10,30,25,60,20,70,10,80,20,30};
int sum = 355;
for(int a=0;i<5;i++){
    int rand = (int)(Math.random()*sum);
    int s=0;//temp cumulative sum
    int i=0;
    while( (s+=Weight[i])<rand)i++;
    result.add(Select[i]);

    sum-=Weight[i];//total weight is lower now
    Weight[i]=0;//if weight is 0 it will never be selected

}

edit: fixed so I don't subtract 0 from sum

I guess each time you remove the duplicates, you must also update your weightSum array.

I'm not really understanding your problem, but your algorithm sounds right: you should be doing something like storing each generated value in a list (based on random number generator), but first check to see if that number already exists in the list before adding it. Repeat until the list has 5 numbers.

My statistics memory is a bit fuzzy, but I think what you want to do is remove the element from consideration after it's been selected. In other words, after selecting the entry, remove that entry from weightSum and subtract its Weight from all subsequent entries and the range of the random number. Might be easier to manage if you work with ArrayLists instead of primitive arrays.