Vážený náhodný výběr

Napište funkci, která přijímá pole dvojic [(položka, váha), ...] a vrací náhodně položku z tohoto seznamu. Pokud bychom v poli měli 3 položky, kde první dvě mají váhu 0.25 a třetí váhu 0.5 a funkci zavolali víckrát za sebou, měli bychom získat z 50 % získat právě třetí položku, z 25 % první a z 25 % druhou.

from collections.abc import Sequence
from typing import TypeVar

T = TypeVar("T")

# data = (id, váha)
data: list[tuple[int, float]] = [
    (1, 0.2),
    (2, 0.15),
    (3, 0.45),
    (4, 0.1),
    (5, 0.025),
    (6, 0.025)
]

def weighted_random(data: Sequence[tuple[T, float]]) -> T:

    """
    Vybere jednu položku podle vah.
    data: sekvence dvojic (hodnota, váha)
    váhy musí být nezáporné
    alespoň jedna váha musí být > 0
    váhy nemusí být normalizované
    """

• Jaká je časová a paměťová složitost vámi navrhovaného řešení?
• Co se změní, když váhy nebudou normalizované?