I recently wrote some code that I thought very inefficient, but since it included only a few values, I accepted it. However, I'm still interested at a better algorithm for the following:
- A list of X objects, each of them are assigned a "weight"
- Sum up the weights
- Generate a random number from 0 to the sum
- Iterate through the objects, subtracting their weight from the sum until the sum is non-positive
- Remove the object from the list, and then add it to the end of the new list
Items 2,4, and 5 all take
n time, and so it is an
Can this be improved?
As an example of a weighted shuffle, an element has a greater chance at being at the front with a higher weight.
Example (I'll generate random numbers to make it real):
6 objects with weights 6,5,4,3,2,1; Sum is 21
I picked 19:
19-6-5-4-3-2 = -1, thus 2 goes in the first position, weights are now 6,5,4,3,1; Sum is 19
I picked 16:
16-6-5-4-3 = -2, thus 3 goes in the second position, weights are now 6,5,4,1; Sum is 16
I picked 3:
3-6 = -3, thus 6 goes in the third position, weights are now 5,4,1; Sum is 10
I picked 8:
8-5-4 = -1, thus 4 goes in the fourth position, weights are now 5,1; Sum is 6
I picked 5:
5-5=0, thus 5 goes in the fifth position, weights are now 1; Sum is 1
I picked 1:
1-1=0, thus 1 goes in the last position, I have no more weights, I finish