Constant-Time Weighted Pick with an Alias Table
Problem statement
You are given positive integer weights weights. A random pick should return index i with probability weights[i] / S, where S is the sum of all weights, and each pick must take constant time. Build an alias table once, then answer each pick with one table lookup.
Let n = weights.length. Think of n columns, each holding exactly S tickets. Index i owns units[i] = weights[i] · n tickets in total, so all indices together own n · S tickets, exactly enough to fill every column. Each column c ends up with two numbers: keep[c], the number of its tickets that belong to index c, and alias[c], the index that owns the other S - keep[c] tickets.
Build the table with two first-in, first-out queues:
- Go through the indices in increasing order. Put index
iat the back ofSmallifunits[i] < S, and at the back ofLargeotherwise (so an index with exactlySunits starts inLarge). - While both queues are non-empty: remove
sfrom the front ofSmallandlfrom the front ofLarge. Setkeep[s] = units[s]andalias[s] = l. Indexlfills the rest of columns, so subtractS - units[s]fromunits[l]. Then putlat the back ofSmallifunits[l] < S, or at the back ofLargeotherwise. - Every index still in either queue gets
keep[i] = Sandalias[i] = i.
A real random pick chooses a column uniformly and then a ticket uniformly. So that answers can be checked, the random numbers are given to you: draws[j] = [c, r] names column c and ticket r, with 0 <= r < S. The pick is c if r < keep[c], and alias[c] otherwise.
Return the picked index for every draw, in order.
Function
pickIndices(weights: int[], draws: int[][]) → int[]Examples
Example 1
weights = [1,3]draws = [[0,0],[0,1],[0,2],[0,3],[1,0],[1,3]]return = [0,0,1,1,1,1]Here n = 2 and S = 4, so index 0 has 1 · 2 = 2 units and index 1 has 3 · 2 = 6 units, and each column holds 4 units.
- Small = [0] and Large = [1]. Pair 0 with 1:
keep[0] = 2,alias[0] = 1, and index 1 gives away4 - 2 = 2units, leaving 4. That is not less than 4, so 1 goes back to Large. - Small is now empty, so index 1 is left over:
keep[1] = 4,alias[1] = 1. - Column 0: tickets 0 and 1 are below
keep[0] = 2and pick 0; tickets 2 and 3 pickalias[0] = 1. Column 1 always picks 1. - Over all 8 (column, ticket) pairs, index 0 is picked 2 times and index 1 is picked 6 times, which is the ratio 1 : 3.
Example 2
weights = [2,1,1,4]draws = [[1,3],[1,4],[2,5],[0,3],[0,6],[3,7]]return = [1,0,3,0,3,3]Here n = 4 and S = 8. The units are [8, 4, 4, 16], so Small = [1, 2] and Large = [0, 3]. Index 0 has exactly 8 units, so it starts in Large.
- Pair 1 with 0:
keep[1] = 4,alias[1] = 0. Index 0 drops to8 - 4 = 4, which is less than 8, so it moves to the back of Small: Small = [2, 0], Large = [3]. - Pair 2 with 3:
keep[2] = 4,alias[2] = 3. Index 3 drops to 12 and goes back to Large. - Pair 0 with 3:
keep[0] = 4,alias[0] = 3. Index 3 drops to 8 and goes back to Large. - Small is empty, so
keep[3] = 8,alias[3] = 3. The table iskeep = [4, 4, 4, 8],alias = [3, 0, 3, 3]. - The draws pick:
[1, 3]→ 1 (3 < 4),[1, 4]→ 0,[2, 5]→ 3,[0, 3]→ 0,[0, 6]→ 3,[3, 7]→ 3.
Example 3
weights = [5]draws = [[0,0],[0,4]]return = [0,0]With one index, S = 5 and index 0 has exactly 5 units. Small is empty, so keep[0] = 5 and every ticket from 0 to 4 picks index 0.
Constraints
1 <= weights.length <= 10^41 <= weights[i] <= 10^51 <= draws.length <= 3000draws[j].length == 20 <= draws[j][0] < weights.length0 <= draws[j][1] < S, whereSis the sum ofweights