Tournament method in Python
Find the maximum with a knockout tournament, then the second largest among the elements that lost only to the maximum.
- File
tournament_method.py, 43 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tournament-method/. The authors are listed in prov/RB2RMG.jsonl.
from typing import Protocol, Sequence, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def tournament_second(a: Sequence[T]) -> tuple[T, T]:
"""Return (largest, second largest) of a, with n + ceil(lg n) - 2 comparisons at most.
The second largest is the item of rank n - 1 in sorted order, so it equals
the largest when the largest occurs twice. Uses only the operator <.
"""
n = len(a)
if n < 2:
raise ValueError("need at least two items")
players = list(range(n)) # @line L1
beaten: list[list[int]] = [[] for _ in range(n)] # @line L1
while len(players) > 1: # @line L2
nxt: list[int] = [] # @line L3
for j in range(0, len(players) - 1, 2): # @line L4
u, v = players[j], players[j + 1] # @line L5
if not a[u] < a[v]: # @line L6
w, l = u, v # @line L6
else:
w, l = v, u # @line L6
beaten[w].append(l) # @line L7
nxt.append(w) # @line L7
if len(players) % 2 == 1: # @line L8
nxt.append(players[-1]) # @line L8
players = nxt # @line L9
m = players[0] # @line L10
s = beaten[m][0] # @line L11
for i in beaten[m][1:]: # @line L12
if a[s] < a[i]: # @line L12
s = i # @line L12
return a[m], a[s] # @line L13
test_tournament_method.py 65 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tournament-method/. The authors are listed in prov/RB2RMG.jsonl.
import random
import pytest
from tournament_method import tournament_second
class Counted:
"""An int wrapper that counts calls of <."""
count = 0
def __init__(self, v: int) -> None:
self.v = v
def __lt__(self, other: "Counted") -> bool:
Counted.count += 1
return self.v < other.v
def comparisons(a: list[int]) -> tuple[int, int, int]:
Counted.count = 0
big, second = tournament_second([Counted(x) for x in a])
return big.v, second.v, Counted.count
def ceil_lg(n: int) -> int:
return (n - 1).bit_length()
def test_examples() -> None:
assert tournament_second([7, 2, 9, 4, 1, 8, 3, 6]) == (9, 8)
assert tournament_second([9, 8, 1, 2, 3, 4, 5, 6]) == (9, 8)
assert comparisons([7, 2, 9, 4, 1, 8, 3, 6])[2] == 9
def test_edges() -> None:
assert tournament_second([1, 2]) == (2, 1)
assert tournament_second([5, 5]) == (5, 5)
assert tournament_second([3, 7, 7]) == (7, 7)
with pytest.raises(ValueError):
tournament_second([1])
def test_comparison_bound() -> None:
rng = random.Random(9)
for n in range(2, 140):
for _ in range(5):
a = rng.sample(range(1000), n)
c = comparisons(a)[2]
assert c <= n + ceil_lg(n) - 2
if n & (n - 1) == 0:
assert c == n + ceil_lg(n) - 2
def test_random_against_sorted() -> None:
rng = random.Random(1932)
for _ in range(1000):
n = rng.randint(2, 70)
a = [rng.randint(-10, 10) for _ in range(n)]
b = sorted(a)
assert tournament_second(a) == (b[-1], b[-2])
What the next level needs
- the tests did not run in this build