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: List[Any]) -> Mapping[Any, int]:
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: Sequence[Any]):
205 Returns all permutations of a sequence; takes O(N^2) time.
207 >>> for x in permute('cat'):
217 yield from _permute(seq, "")
220 def _permute(seq: Sequence[Any], path):
224 for i in range(len(seq)):
229 yield from _permute(cdr, path + car)
233 lst: Sequence[Any], target: Any, *, sanity_check=False
234 ) -> Tuple[bool, int]:
235 """Performs a binary search on lst (which must already be sorted).
236 Returns a Tuple composed of a bool which indicates whether the
237 target was found and an int which indicates the index closest to
238 target whether it was found or not.
240 >>> a = [1, 4, 5, 6, 7, 9, 10, 11]
241 >>> binary_search(a, 4)
244 >>> binary_search(a, 12)
247 >>> binary_search(a, 3)
250 >>> binary_search(a, 2)
254 >>> binary_search(a, 4, sanity_check=True)
255 Traceback (most recent call last):
264 assert x >= last # This asserts iff the list isn't sorted
265 last = x # in ascending order.
266 return _binary_search(lst, target, 0, len(lst) - 1)
270 lst: Sequence[Any], target: Any, low: int, high: int
271 ) -> Tuple[bool, int]:
273 mid = (high + low) // 2
274 if lst[mid] == target:
276 elif lst[mid] > target:
277 return _binary_search(lst, target, low, mid - 1)
279 return _binary_search(lst, target, mid + 1, high)
284 if __name__ == '__main__':