All problems
Top-p (Nucleus) Filtering
Problem
Return the smallest set of tokens whose probabilities sum to at least p, taken in descending probability order with ties broken by original index.
The result is a list of [token, probability] pairs in that order. An empty input yields an empty list.
Hint
Stop as soon as the running probability mass reaches p.
Test cases
case 1
in: [["a","b","c","d"],[0.4,0.3,0.2,0.1],0.5]
expected: [["a",0.4],["b",0.3]]
case 2
in: [["a","b","c","d"],[0.25,0.25,0.25,0.25],0.5]
expected: [["a",0.25],["b",0.25]]
case 3
in: [["a","b","c","d"],[0.25,0.25,0.25,0.25],0.9]
expected: [["a",0.25],["b",0.25],["c",0.25],["d",0.25]]
case 4
in: [["a","b"],[0.9,0.1],0.1]
expected: [["a",0.9]]
case 5
in: [[],[],0.5]
expected: []
Starter codePython
def top_p_filtering(tokens, probs, p):
# Your code here
pass5 test cases · run your code against them in the editor