Weighted Random Selection Algorithm
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 528. Random Pick with Weight | 🟠 |
Prerequisite Knowledge
Before reading this article, you should first learn about:
The reason for writing this article comes from playing the mobile game LOL. I have a friend who complained that his ranked match teammates were too weak. I told him that I found my teammates quite capable in ranked matches, not really dragging me down.
My friend then said something intriguing: usually, players with higher hidden scores, if they can't be matched with equally skilled teammates, will end up with some weaker players.
Hmm? I thought for a few seconds and felt something was off. Was he implying that my hidden score was low, or was he saying I was the weak player?
I immediately challenged him to a match to prove I wasn't the weak player, but rather he was. The results of that match are best left unsaid—take a guess.
After the match, I decided to write this post because I had some thoughts about the game's matchmaking mechanism.
The so-called "hidden score" might be real or not, as the matchmaking mechanism is a core component of any competitive game. It's likely very complex, not something that can be determined by a few simple metrics.
However, simplifying this "hidden score" mechanism presents an interesting algorithm problem: how does the system perform matching with different probabilities?
Or more simply, how do you make a weighted random selection?
This might seem easy. If you have an array of length n, and you want to randomly pick an element with equal probability, you would simply generate a random number between [0, n-1] as the index. Each element would have a probability of 1/n of being chosen.
But what if each element has a different weight, and the size of the weight represents the probability of randomly selecting that element? How would you write an algorithm to randomly select an element based on these weights?
LeetCode problem 528 "Random Pick with Weight" is exactly such a problem:
528. Random Pick with Weight | LeetCode |
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
- For example, if
w = [1, 3], the probability of picking index0is1 / (1 + 3) = 0.25(i.e.,25%), and the probability of picking index1is3 / (1 + 3) = 0.75(i.e.,75%).
Example 1:
Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0] Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0] Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4. Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on.
Constraints:
1 <= w.length <= 1041 <= w[i] <= 105pickIndexwill be called at most104times.
Let's think about this problem and solve the issue of selecting elements randomly according to their weights.