return lst
-def population_counts(lst: List[Any]) -> Mapping[Any, int]:
+def population_counts(lst: List[Any]) -> Counter:
"""
Return a population count mapping for the list (i.e. the keys are
list items and the values are the number of occurrances of that
yield lst[i : i + n]
-def permute(seq: Sequence[Any]):
+def permute(seq: str):
"""
- Returns all permutations of a sequence; takes O(N^2) time.
+ Returns all permutations of a sequence; takes O(N!) time.
>>> for x in permute('cat'):
... print(x)
yield from _permute(seq, "")
-def _permute(seq: Sequence[Any], path):
- if len(seq) == 0:
+def _permute(seq: str, path: str):
+ seq_len = len(seq)
+ if seq_len == 0:
yield path
- for i in range(len(seq)):
+ for i in range(seq_len):
car = seq[i]
left = seq[0:i]
right = seq[i + 1 :]
yield from _permute(cdr, path + car)
-def binary_search(lst: Sequence[Any], target: Any, *, sanity_check=False) -> Tuple[bool, int]:
+def binary_search(
+ lst: Sequence[Any], target: Any, *, sanity_check=False
+) -> Tuple[bool, int]:
"""Performs a binary search on lst (which must already be sorted).
Returns a Tuple composed of a bool which indicates whether the
target was found and an int which indicates the index closest to