from collections import Counter
from itertools import islice
-from typing import Any, Iterator, List, Mapping, Sequence
+from typing import Any, Iterator, List, Mapping, Sequence, Tuple
def shard(lst: List[Any], size: int) -> Iterator[Any]:
yield lst[i:i + n]
+def permute(seq: Sequence[Any]):
+ """
+ Returns all permutations of a sequence; takes O(N^2) time.
+
+ >>> for x in permute('cat'):
+ ... print(x)
+ cat
+ cta
+ act
+ atc
+ tca
+ tac
+
+ """
+ yield from _permute(seq, "")
+
+
+def _permute(seq: Sequence[Any], path):
+ if len(seq) == 0:
+ yield path
+
+ for i in range(len(seq)):
+ car = seq[i]
+ left = seq[0:i]
+ right = seq[i + 1:]
+ cdr = left + right
+ yield from _permute(cdr, path + car)
+
+
+def binary_search(lst: Sequence[Any], target: Any) -> 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
+ target whether it was found or not.
+
+ >>> a = [1, 4, 5, 6, 7, 9, 10, 11]
+ >>> binary_search(a, 4)
+ (True, 1)
+
+ >>> binary_search(a, 12)
+ (False, 8)
+
+ >>> binary_search(a, 3)
+ (False, 1)
+
+ >>> binary_search(a, 2)
+ (False, 1)
+
+ """
+ return _binary_search(lst, target, 0, len(lst) - 1)
+
+
+def _binary_search(lst: Sequence[Any], target: Any, low: int, high: int) -> Tuple[bool, int]:
+ if high >= low:
+ mid = (high + low) // 2
+ if lst[mid] == target:
+ return (True, mid)
+ elif lst[mid] > target:
+ return _binary_search(lst, target, low, mid - 1)
+ else:
+ return _binary_search(lst, target, mid + 1, high)
+ else:
+ return (False, low)
+
+
if __name__ == '__main__':
import doctest
doctest.testmod()