3 from collections import Counter
4 from itertools import islice
5 from typing import Any, Iterator, List, Mapping, Sequence, Tuple
8 def shard(lst: List[Any], size: int) -> Iterator[Any]:
10 Yield successive size-sized shards from lst.
12 >>> for sublist in shard([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 3):
13 ... [_ for _ in sublist]
20 for x in range(0, len(lst), size):
21 yield islice(lst, x, x + size)
24 def flatten(lst: List[Any]) -> List[Any]:
28 >>> flatten([ 1, [2, 3, 4, [5], 6], 7, [8, [9]]])
29 [1, 2, 3, 4, 5, 6, 7, 8, 9]
34 if isinstance(lst[0], list):
35 return flatten(lst[0]) + flatten(lst[1:])
36 return lst[:1] + flatten(lst[1:])
39 def prepend(item: Any, lst: List[Any]) -> List[Any]:
41 Prepend an item to a list.
43 >>> prepend('foo', ['bar', 'baz'])
51 def remove_list_if_one_element(lst: List[Any]) -> Any:
53 Remove the list and return the 0th element iff its length is one.
55 >>> remove_list_if_one_element([1234])
58 >>> remove_list_if_one_element([1, 2, 3, 4])
68 def population_counts(lst: Sequence[Any]) -> Counter:
70 Return a population count mapping for the list (i.e. the keys are
71 list items and the values are the number of occurrances of that
72 list item in the original list.
74 >>> population_counts([1, 1, 1, 2, 2, 3, 3, 3, 4])
75 Counter({1: 3, 3: 3, 2: 2, 4: 1})
81 def most_common(lst: List[Any], *, count=1) -> Any:
84 Return the most common item in the list. In the case of ties,
85 which most common item is returned will be random.
87 >>> most_common([1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4])
90 >>> most_common([1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4], count=2)
94 p = population_counts(lst)
95 return remove_list_if_one_element([_[0] for _ in p.most_common()[0:count]])
98 def least_common(lst: List[Any], *, count=1) -> Any:
100 Return the least common item in the list. In the case of
101 ties, which least common item is returned will be random.
103 >>> least_common([1, 1, 1, 2, 2, 3, 3, 3, 4])
106 >>> least_common([1, 1, 1, 2, 2, 3, 3, 3, 4], count=2)
110 p = population_counts(lst)
111 mc = p.most_common()[-count:]
113 return remove_list_if_one_element([_[0] for _ in mc])
116 def dedup_list(lst: List[Any]) -> List[Any]:
118 Remove duplicates from the list performantly.
120 >>> dedup_list([1, 2, 1, 3, 3, 4, 2, 3, 4, 5, 1])
124 return list(set(lst))
127 def uniq(lst: List[Any]) -> List[Any]:
129 Alias for dedup_list.
131 return dedup_list(lst)
134 def contains_duplicates(lst: List[Any]) -> bool:
136 Does the list contian duplicate elements or not?
138 >>> lst = [1, 2, 1, 3, 3, 4, 4, 5, 6, 1, 3, 4]
139 >>> contains_duplicates(lst)
142 >>> contains_duplicates(dedup_list(lst))
154 def all_unique(lst: List[Any]) -> bool:
156 Inverted alias for contains_duplicates.
158 return not contains_duplicates(lst)
161 def transpose(lst: List[Any]) -> List[Any]:
163 Transpose a list of lists.
165 >>> lst = [[1, 2], [3, 4], [5, 6]]
167 [[1, 3, 5], [2, 4, 6]]
170 transposed = zip(*lst)
171 return [list(_) for _ in transposed]
174 def ngrams(lst: Sequence[Any], n):
176 Return the ngrams in the sequence.
178 >>> seq = 'encyclopedia'
179 >>> for _ in ngrams(seq, 3):
192 >>> seq = ['this', 'is', 'an', 'awesome', 'test']
193 >>> for _ in ngrams(seq, 3):
196 ['is', 'an', 'awesome']
197 ['an', 'awesome', 'test']
199 for i in range(len(lst) - n + 1):
203 def permute(seq: str):
205 Returns all permutations of a sequence; takes O(N!) time.
207 >>> for x in permute('cat'):
217 yield from _permute(seq, "")
220 def _permute(seq: str, path: str):
225 for i in range(seq_len):
230 yield from _permute(cdr, path + car)
234 lst: Sequence[Any], target: Any, *, sanity_check=False
235 ) -> Tuple[bool, int]:
236 """Performs a binary search on lst (which must already be sorted).
237 Returns a Tuple composed of a bool which indicates whether the
238 target was found and an int which indicates the index closest to
239 target whether it was found or not.
241 >>> a = [1, 4, 5, 6, 7, 9, 10, 11]
242 >>> binary_search(a, 4)
245 >>> binary_search(a, 12)
248 >>> binary_search(a, 3)
251 >>> binary_search(a, 2)
255 >>> binary_search(a, 4, sanity_check=True)
256 Traceback (most recent call last):
265 assert x >= last # This asserts iff the list isn't sorted
266 last = x # in ascending order.
267 return _binary_search(lst, target, 0, len(lst) - 1)
271 lst: Sequence[Any], target: Any, low: int, high: int
272 ) -> Tuple[bool, int]:
274 mid = (high + low) // 2
275 if lst[mid] == target:
277 elif lst[mid] > target:
278 return _binary_search(lst, target, low, mid - 1)
280 return _binary_search(lst, target, mid + 1, high)
285 if __name__ == '__main__':