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)
232 def binary_search(lst: Sequence[Any], target: Any) -> Tuple[bool, int]:
233 """Performs a binary search on lst (which must already be sorted).
234 Returns a Tuple composed of a bool which indicates whether the
235 target was found and an int which indicates the index closest to
236 target whether it was found or not.
238 >>> a = [1, 4, 5, 6, 7, 9, 10, 11]
239 >>> binary_search(a, 4)
242 >>> binary_search(a, 12)
245 >>> binary_search(a, 3)
248 >>> binary_search(a, 2)
252 return _binary_search(lst, target, 0, len(lst) - 1)
255 def _binary_search(lst: Sequence[Any], target: Any, low: int, high: int) -> Tuple[bool, int]:
257 mid = (high + low) // 2
258 if lst[mid] == target:
260 elif lst[mid] > target:
261 return _binary_search(lst, target, low, mid - 1)
263 return _binary_search(lst, target, mid + 1, high)
268 if __name__ == '__main__':