Alias Table Build

Problem

Build Walker's alias table for a discrete distribution over probs. Return [prob, alias] where prob[i] is the probability of keeping column i and alias[i] is the fallback column. Return [[], []] for an empty or all-zero distribution.

Hint

Pair small columns with large ones, moving the surplus into the large column.

Test cases

case 1

in: [[0.5,0.5]]

expected: [[1,1],[0,1]]

case 2

in: [[0.7,0.3]]

expected: [[1,0.6],[0,0]]

case 3

in: [[0.3333333333333333,0.3333333333333333,0.3333333333333333]]

expected: [[1,1,1],[0,1,2]]

case 4

in: [[1]]

expected: [[1],[0]]

case 5

in: [[0.1,0.2,0.7]]

expected: [[0.30000000000000004,0.6000000000000001,1],[2,2,2]]

case 6

in: [[0.5,0.25,0.25]]

expected: [[1,0.75,0.75],[0,0,0]]

Starter codePython

def alias_table(probs):
    # Your code here
    pass

6 test cases · run your code against them in the editor