Weighted Random Selection Algorithm

labuladongOriginalAbout 2816 words

This article will resolve

LeetCode	Difficulty
528. Random Pick with Weight	🟠

Prerequisites

Before reading this article, you should first learn:

The reason for writing this article is playing the LOL mobile game. A friend of mine complained about the poor skills of teammates in ranked matches. I said my teammates seem quite competent, not dragging me down much.

My friend said something meaningful: Generally, players with high hidden scores, if they can't find teammates of similar skill in ranked matches, will be matched with less skilled players.

Hmm? I thought for a few seconds and felt something was off. Was he implying my hidden score is low, or that I am one of those less skilled players?

I immediately challenged him to a game to prove I am not the less skilled player. The outcome is better left unsaid; you can guess.

After the game, I was inspired to write because I gained some insights into the match-making mechanism.

I am not sure if the concept of "hidden scores" is real, as the match-making mechanism is a core part of any competitive game and likely very complex, not just determined by a few simple metrics.

However, simplifying this "hidden score" mechanism presents an interesting algorithm problem: How does the system match players with different probabilities?

Or more simply, how to perform random selection with weights?

Don't think this is easy. If given an array of length n, you can randomly pick an element with equal probability by generating a random number [0, n-1] as an index, where each element has a probability of 1/n of being chosen.

But if each element has a different weight, with the weight indicating the probability of the element being chosen, how would you write an algorithm to randomly pick an element?

LeetCode problem 528 "Random Pick with Weight" addresses this issue:

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 i^th 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 index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (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 <= 10⁴
1 <= w[i] <= 10⁵
pickIndex will be called at most 10⁴ times.

Let's explore this problem and solve the issue of randomly selecting elements based on weight.

Weighted Random Selection Algorithm

528. 按权重随机选择 https://leetcode.cn/problems/random-pick-with-weight

528. Random Pick with Weight https://leetcode.com/problems/random-pick-with-weight

剑指 Offer II 071. 按权重生成随机数 https://leetcode.cn/problems/cuyjEf

剑指 Offer II 071. 按权重生成随机数 https://leetcode.com/problems/cuyjEf

Solution Approach

Solution Code