Weighted Sampling from Score Distribution

Given a list of strings and their scores (real-valued, distributed over the full real line), draw a single sample where the probability of each string is proportional to a normalized version of its score. The numerical-stability discussion (softmax over arbitrary reals) is part of the signal. Requirements Input: items: list[str], scores: list[float]. Scores may be negative, very large, or very small. Return one item with probability derived from its score. Clarify the score-to-weight transform; softmax is the safest default for arbitrary real logits. Notes Convert finite scores with w_i = exp(s_i - max_score). Subtracting the maximum prevents overflow while preserving ratios. If every score is equal, the result is uniform. Define a rejection policy for NaN and for an all--inf input. If linear shifting is explicitly requested, compute w_i = s_i - min_score; if the resulting total is zero, return a uniform draw instead of dividing by zero. This transform gives the minimum-scored items zero probability, so confirm that semantic. For CDF inversion, build cumulative positive weights, draw u from [0, total_weight), and choose the first cumulative sum strictly greater than u (bisect_right). The strict comparison prevents a zero-weight prefix from being selected when u == 0. Setup is O(n), and each draw is O(log n). For many draws, the alias method gives O(1) sampling after O(n) preprocessing. Weighted sampling without replacement needs a different algorithm such as exponential keys. Preparation Implement stable softmax and CDF inversion, including all-equal, zero-weight-prefix, NaN, and all--inf tests. Hand-walk weights [0, 1, 3] at u = 0, at an exact bucket boundary, and just below the total. Explain the preprocessing/query trade-off between CDF and alias sampling. Sketch exponential-key sampling for a without-replacement follow-up.