Geek Answers Handbook

Algorithm for weighted random selection O (1) with deletion

I am looking for a weighted random selection algorithm with similar characteristics for the method, except when the items are deleted after they are selected.

For example, I have a bag that produces:

  • Red marble in 70% of cases.
  • Green marble in 10% of cases.
  • And blue marble in 20% of cases.

I try the bag and get red marble. Red is now removed, so I assume the bag will now produce:

  • Green marble is 33% of the time.
  • Blue marble is 66% of the time.

I believe that you could precompile the tree of any possible probability table, so the sample is still O(1) . Are smarter algorithms for time-weighted selection with deletion?

+7
algorithm probability
source share
1 answer

Actually, it seems I misunderstood the question. I did not know about the alias method, and the answer below is not a similar algorithm. I will leave my answer here because it is still informative.

I do not know the O (1) algorithm, but it is easy to execute in the search log (N) 2 and the update log (N). This could probably be improved with a more specific algorithm.

Put your elements in the Fenwick tree with their probabilities as their values. Also, when changing elements, the total cumulative probability is taken into account.

Now we can do better than just delete items! We can arbitrarily change the element probability, but setting the element probability to 0 is equivalent to deleting it. You can then query the log (N) cumulative probability of the nth element. This logically extends to the binary search of the first (elementary) logarithm of (N) 2 with a cumulative probability greater than p.

Now, to make a weighted random choice, we generate a number p between 0 and P, where P is the total cumulative probability. Then we perform the binary search described above to find and select the first element with a cumulative probability greater than p.

I improved this because using the Fenwick tree it is easy to do a log search (N) for the first element with a total probability greater than or equal to p. I can highly recommend reading this explanation of Fenwick trees .

Simply put, to find an element, do a normal binary search on the Fenwick tree, like on any other tree, except that you save the current total amount (starting from 0). Whenever you select a child of the right hand in a binary search, increase the current total by the value of the current node. Then, comparing the value of the current node with the total amount, we want to add the current value of the node to the sum before comparison.

+3
source share

More articles:


All Articles