+ Transpose a list of lists.
+
+ >>> lst = [[1, 2], [3, 4], [5, 6]]
+ >>> transpose(lst)
+ [[1, 3, 5], [2, 4, 6]]
+
+ """
+ transposed = zip(*lst)
+ return [list(_) for _ in transposed]
+
+
+def ngrams(lst: Sequence[Any], n):
+ """
+ Return the ngrams in the sequence.
+
+ >>> seq = 'encyclopedia'
+ >>> for _ in ngrams(seq, 3):
+ ... _
+ 'enc'
+ 'ncy'
+ 'cyc'
+ 'ycl'
+ 'clo'
+ 'lop'
+ 'ope'
+ 'ped'
+ 'edi'
+ 'dia'
+
+ >>> seq = ['this', 'is', 'an', 'awesome', 'test']
+ >>> for _ in ngrams(seq, 3):
+ ... _
+ ['this', 'is', 'an']
+ ['is', 'an', 'awesome']
+ ['an', 'awesome', 'test']
+ """
+ for i in range(len(lst) - n + 1):
+ yield lst[i : i + n]
+
+
+def permute(seq: str):
+ """
+ Returns all permutations of a sequence; takes O(N!) time.
+
+ >>> for x in permute('cat'):
+ ... print(x)
+ cat
+ cta
+ act
+ atc
+ tca
+ tac
+
+ """
+ yield from _permute(seq, "")
+
+
+def _permute(seq: str, path: str):
+ seq_len = len(seq)
+ if seq_len == 0:
+ yield path
+
+ for i in range(seq_len):
+ car = seq[i]
+ left = seq[0:i]
+ right = seq[i + 1 :]
+ cdr = left + right
+ yield from _permute(cdr, path + car)
+
+
+def shuffle(seq: MutableSequence[Any]) -> MutableSequence[Any]:
+ """Shuffles a sequence into a random order.
+
+ >>> random.seed(22)
+ >>> shuffle([1, 2, 3, 4, 5])
+ [3, 4, 1, 5, 2]
+
+ >>> shuffle('example')
+ 'empaelx'
+
+ """
+ if isinstance(seq, str):
+ import string_utils
+
+ return string_utils.shuffle(seq)
+ else:
+ random.shuffle(seq)
+ return seq
+
+
+def scramble(seq: MutableSequence[Any]) -> MutableSequence[Any]:
+ return shuffle(seq)
+
+
+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
+ 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)
+
+ >>> a.append(9)
+ >>> binary_search(a, 4, sanity_check=True)
+ Traceback (most recent call last):
+ ...
+ AssertionError
+
+ """
+ if sanity_check:
+ last = None
+ for x in lst:
+ if last is not None:
+ assert x >= last # This asserts iff the list isn't sorted
+ last = x # in ascending order.
+ 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)
+
+
+def powerset(lst: Sequence[Any]) -> Iterator[Sequence[Any]]:
+ """Returns the powerset of the items in the input sequence.
+
+ >>> for x in powerset([1, 2, 3]):
+ ... print(x)
+ ()
+ (1,)
+ (2,)
+ (3,)
+ (1, 2)
+ (1, 3)
+ (2, 3)
+ (1, 2, 3)
+ """
+ return chain.from_iterable(combinations(lst, r) for r in range(len(lst) + 1))