65 lines
2.2 KiB
Python
65 lines
2.2 KiB
Python
"""Boyer-Moore majority vote: the element occurring more than n/2 times.
|
|
|
|
Three outcomes, three channels -- the caller can always tell them apart:
|
|
|
|
- empty input -> raise EmptySequence (a ValueError)
|
|
- no element occurs > n/2 -> raise NoMajority (a ValueError)
|
|
- otherwise -> return the element itself, which may be
|
|
None, float('nan'), or any other object.
|
|
|
|
The old contract returned None for all three, so a None majority, an empty
|
|
list and a no-majority list were one value.
|
|
|
|
The confirmation pass counts with `_same`, not `list.count`: identity first,
|
|
then NaN == NaN, then `==`. That is what lets a non-reflexive element be
|
|
confirmed when it fills the list -- repeated NaN objects count as equal even
|
|
though `nan != nan`, and a repeated object whose `__eq__` always answers False
|
|
is still recognised by identity. Note that distinct objects of such a class
|
|
are *not* conflated: only identity, NaN-ness and `==` count. Python's own
|
|
equality still rules elsewhere, so `True` and `1` remain one value.
|
|
|
|
Boyer-Moore's first pass is unchanged: O(n) time, O(1) extra space, one
|
|
materialisation of the iterable (so a generator is accepted).
|
|
"""
|
|
from __future__ import annotations
|
|
from typing import Any, Iterable
|
|
|
|
|
|
class EmptySequence(ValueError):
|
|
"""majority() was given nothing to vote on."""
|
|
|
|
|
|
class NoMajority(ValueError):
|
|
"""No element occurs more than len(seq) // 2 times."""
|
|
|
|
|
|
def _same(a: Any, b: Any) -> bool:
|
|
"""The counting relation: identity, then NaN equality, then `==`."""
|
|
if a is b:
|
|
return True
|
|
if isinstance(a, float) and isinstance(b, float) and a != a and b != b:
|
|
return True
|
|
return a == b
|
|
|
|
|
|
def majority(nums: Iterable[Any]) -> Any:
|
|
arr = list(nums)
|
|
if not arr:
|
|
raise EmptySequence("majority() of an empty sequence")
|
|
cand = arr[0]
|
|
count = 0
|
|
for x in arr:
|
|
if count == 0:
|
|
cand = x
|
|
count = 1
|
|
elif _same(x, cand):
|
|
count += 1
|
|
else:
|
|
count -= 1
|
|
if sum(1 for x in arr if _same(x, cand)) * 2 > len(arr):
|
|
return cand
|
|
raise NoMajority(
|
|
"no element occurs more than %d times in a %d-element sequence"
|
|
% (len(arr) // 2, len(arr))
|
|
)
|