Sample from weighted outcomes

Turn random numbers into choices: sample from outcomes with given weights, and count what came out.

What to build

A program that samples a categorical distribution for each draw and counts the outcomes.

Requirements

  • Probabilities are the weights divided by their sum, in the given order.
  • For each draw r, choose the first outcome whose running total is greater than r.
  • Print the chosen outcomes on one line, then one line LABEL COUNT per outcome, in the given order.

Input

Line 1: the outcome labels. Line 2: their weights. Line 3: the draws, numbers from 0 up to (not including) 1.

Output

The samples, then the counts.

Constraints

1 to 50 outcomes, weights ≥ 0 with a positive sum; 1 to 1000 draws.

Example

Input:

sun rain snow
6 3 1
0.1 0.65 0.95 0.59 0.6

Output:

sun rain snow sun rain
sun 2
rain 2
snow 1

Why it works

Outcome k owns the interval from the total of the earlier probabilities up to that total plus its own, so a draw lands there with exactly its probability.

Examples

Example 1 · Input
sun rain snow
6 3 1
0.1 0.65 0.95 0.59 0.6
Expected output
sun rain snow sun rain
sun 2
rain 2
snow 1
Example 2 · Input
x y
1 1
0.25 0.75
Expected output
x y
x 1
y 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Divide each weight by the total to get probabilities.

Hint 2

For each draw r, pick the first outcome whose running total of probabilities is greater than r.

Solution

Show one correct solution (try it yourself first)
labels = input().split()
weights = list(map(float, input().split()))
draws = list(map(float, input().split()))
total = sum(weights)
chosen = []
for r in draws:
    running = 0.0
    pick = labels[-1]
    for label, w in zip(labels, weights):
        running += w / total
        if r < running:
            pick = label
            break
    chosen.append(pick)
print(*chosen)
for label in labels:
    print(label, chosen.count(label))

Lesson: Sampling and randomness →