"""稀疏/稠密结果的 Reciprocal Rank Fusion。"""
from collections import defaultdict


def rrf(*rankings: list[str], k: int = 60) -> list[tuple[str, float]]:
    if k <= 0:
        raise ValueError("k must be positive")
    scores: dict[str, float] = defaultdict(float)
    for ranking in rankings:
        seen = set()
        for rank, doc_id in enumerate(ranking, 1):
            if doc_id in seen:
                continue
            seen.add(doc_id)
            scores[doc_id] += 1.0 / (k + rank)
    return sorted(scores.items(), key=lambda item: (-item[1], item[0]))


if __name__ == "__main__":
    fused = rrf(["A", "B", "C"], ["B", "D", "A"])
    print(fused)
    assert fused[0][0] in {"A", "B"}
    assert len(fused) == 4