Important Update
The Guide Feature will be discontinued after December 15th, 2023. Until then, you can continue to access and refer to the existing guides.
Author avatar

Recnac

Python Tricks - Iterable - Part 2

Recnac

  • Nov 23, 2019
  • 11 Min read
  • 2,219 Views
  • Nov 23, 2019
  • 11 Min read
  • 2,219 Views
Data
Python

Introduction

Editor's note: This guide is part of a series on useful Python tricks. Read more about the series and find links the other guides here.

This is the second of two guides on iterable Python tricks. In the first, we learned many useful iterable Python tricks. Check it out if you missed it.

In this guide, we will continue to add more iterable python tricks to our arsenal.

map

The map function applies a function to all the items in a given iterable.

1map(function, iterables) -> iterables
python

map returns a list of the results after applying the given function to each item of a given iterable.

Inspiring Examples

1"""map to node children recursively"""
2# L104: get depth in binary tree
3def max_depth(root: TreeNode) -> int:
4    return 1 + max(map(maxDepth, (root.left, root.right))) if root else 0
5
6"""comparison map find with map index"""
7# L290: given a pattern and a string words, find if words follows the same pattern. 
8# i.e. pattern = 'abba', words = 'dog cat cat dog'
9def valid_word_pattern(pattern: str, words: str) -> bool:
10    s, t = pattern, words.split()
11    return list(map(s.find, s)) == list(map(t.index, t))
12
13"""map dict.get"""
14# L506: given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal"
15def find_relative_ranks(nums: List[int]) -> List[str]:
16    sorted_nums = sorted(nums, reverse=True)
17    rank = ["Gold Medal", "Silver Medal", "Bronze Medal"] + list(map(str, range(4, len(nums) + 1)))
18    return list(map(dict(zip(sorted_nums, rank)).get, nums))
python

reduce

reduce returns a single value constructed by applying a rolling computation to sequential pairs of values in a given iterable.

1reduce(function, sequence[, initial]) -> value
python

Inspiring Examples

1# L136: every numbers appears twice except for one, find that single one
2def single_number(nums: List[int]) -> int:
3    return reduce(lambda x, y: x ^ y, nums)
4
5# L47: generate all possible permutations
6def permute(nums: List[int]) -> List[List[int]]:
7    return reduce(lambda P, n: [p[:i] + [n] + p[i:] for p in P for i in range(len(p)+1)], nums, [[]])
python

zip

zip takes an iterator that aggregates elements based on the iterables passed and returns an iterator of tuples. Its syntax is as follows:

1zip(*iterables) -> iterator

Notice the iterator stops when the shortest iterable is exhausted. If you prefer to match the longest iterable, you can try zip_longest(*iterables, fillvalue=None) in itertools module.

1a = [1,2,3]
2b = ['one','two','three']
3zipped=zip(a,b)
4list(zipped)
5# output: [(1, 'one'), (2, 'two'), (3, 'three')]
python

Inspiring Examples

1"""construct dict"""
2keys = ['a', 'b', 'c']
3vals = [1, 2, 3]
4zipped_dict = dict(zip(keys, vals))
5
6"""difference of neighbor pairs"""
7arr, diffs = [1, 2, 3, 4, 5], []
8for pre, post in zip(arr[:-1], arr[1:]):  # zip(arr, arr[1:]) is ok too, zip matches the shortest
9    diffs.append(post - pre)
10
11"""transpose matrix"""
12# L867: The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
13def transpose(matrix: List[List[int]]) -> List[List[int]]:
14    return list(map(list, zip(*matrix)))
15
16"""zip into a set"""
17# L290: given a pattern and a string words, find if words follows the same pattern. 
18# i.e. pattern = 'abba', words = 'dog cat cat dog'
19def valid_word_pattern(pattern: str, words: str) -> bool:
20    s, t = pattern, words.split()
21    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)
python

Unpacking

We use the operators * (for tuples) and ** (for dictionaries) to unpack arguments in Python.

1def product(a, b):
2    return a * b
3
4"""use * to unpack tuple, list or other iterables"""
5param_tuple = (2, 3)
6product(*param_tuple)
7# output: 6
8
9"""use ** to unpack dict"""
10param_dict = {'a': 2, 'b': 3}
11product(**param_dict)
12# output: 6
python

Inspiring Examples

More advanced usages of unpacking:

1"""get rest of all"""
2a, *b, c = range(5)
3# b = [1, 2, 3]
4[(c, *d, [*e]), f, *g] = [[1, 2, 3, 4, [5, 5, 5]], 6, 7, 8]
5# d = [2, 3, 4], e = [5, 5, 5], g = [7, 8]
6
7"""merge dicts"""
8a = {'1': 1, '2': 2}
9b = {'2': 3, '4': 4}
10merged_dict = {**a, **b}   #{'1': 1, '2': 3, '4': 4}
11
12"""[*a] = list(a), [*zip(*matrix)]: transpose matrix"""
13# L54: traverse matrix in spiral order.
14def traverse_spiral_order(matrix: List[List[int]]) -> List[int]:
15    return matrix and [*matrix.pop(0)] + traverse_spiral_order([*zip(*matrix)][::-1])
python

sum

The sum function takes an iterable and returns the sum of items in it. Its syntax is as follows:

1sum(iterable[, start]) -> number
python

Inspiring Examples

1"""sum"""
2# L771: S is stones you have, J is types of stones which are jewels, and you want to know how many stones are also jewels.
3def num_jewels_in_stones(J: str, S: str) -> int:
4    return sum(map(J.count, S))
5
6# L389: string t is generated by random shuffling string s and then add one more letter at a random position, find the letter.
7def find_the_difference(s: str, t: str) -> str:
8    return chr(sum(map(ord, t)) - sum(map(ord, s)))
9
10# L266: determine if a permutation of the string could form a palindrome
11def can_permute_palindrome(s: str) -> bool:
12    """at most one odd count character"""
13    return sum(v % 2 for v in Counter(s).values()) <= 1
python

max and min

The max function returns the largest of the input values. Its syntax is as follows:

1max(iterable[, default=obj, key=func]) -> value
python

The min function is similar to this.

Inspiring Examples

1"""max"""
2# L169: find the majority element which appears more than ⌊ n/2 ⌋ times.
3def majority_element(nums: List[int]) -> int:
4    counts = Counter(nums)
5    return max(counts.keys(), key=counts.get)
6
7"""min"""
8# L14: find the longest common prefix string amongst an array of strings.
9def longest_common_prefix(strs: List[str]) -> str:
10    shortest = min(strs, key=len)
11    for i, ch in enumerate(shortest):
12        if any(s[i] != ch for s in strs):
13            return shortest[:i]
14    return shortest
python

any and all

The any function tests whether any item in the iterable evaluates to True to not. Its syntax is as follows:

1any(iterable) -> bool
python

The all function is similar to this.

Inspiring Examples

1"""any"""
2# L36: determine if a 9x9 Sudoku board is valid, which means 1-9 in row, column, 3x3 sub-boxes
3def is_valid_sudoku(board: List[List[str]]) -> bool:
4    seen = set()
5    return not any(x in seen or seen.add(x)
6                   for i, row in enumerate(board)
7                   for j, c in enumerate(row)
8                   if c != '.'
9                   for x in ((c, i), (j, c), (i/3, j/3, c)))
10
11"""all"""
12# L766: a matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
13def is_toeplitz_matrix(matrix: List[List[int]]) -> bool:
14    return all(r == 0 or c == 0 or matrix[r-1][c-1] == val
15               for r, row in enumerate(matrix)
16               for c, val in enumerate(row))
17
18# L246: verify the number is strobogrammatic, strobogrammatic number looks the same when rotated 180 degrees
19def is_strobogrammatic(num: str) -> bool:
20    return all(map('696 00 11 88'.count, map(operator.add, num, num[::-1])))
21
22# L261: given n nodes labeled from 0 to n-1 and a list of undirected edges, check whether these edges make up a valid tree.
23def valid_tree(n: int, edges: List[List[int]]) -> bool:
24    """all check in union find"""
25    parent = range(n)
26    def find(x):
27        return x if parent[x] == x else find(parent[x])
28    def union(xy):
29        x, y = map(find, xy)
30        parent[x] = y
31        return x != y
32    return len(edges) == n-1 and all(map(union, edges))
python

Customize iterable in bisect

bisect module provides support for maintaining a list in sorted order without having to sort the list after each insertion.

The bisect_left/bisect function locates the insertion point for x in a to maintain sorted order.

1bisect.bisect_left(a, x[, lo=0, hi=len(a)]) -> int
python

Inspiring Examples

In the following examples, bisect usage is generalized to customized iterables. The key point is the idea of constructing an appropriate iterable. We need to use __getitem__ for bisect to index.

1"""use binary search to find the first number that's less than or equal to the last."""
2# L153: find the minimum element in rotated sorted array
3def find_min_in_rotated_sorted_arr(self, nums: List[int]) -> int:
4    """construct iterable which distinguish the two parts of rotated array"""
5    self.__getitem__ = lambda i: nums[i] <= nums[-1]
6    return nums[bisect.bisect(self, False, 0, len(nums))]
7
8"""construct a boolean iterable and use binary search"""
9# L4: find the median of the two sorted arrays
10def find_median_in_two_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
11    a, b = sorted((nums1, nums2), key=len)
12    m, n = len(a), len(b)
13    after = (m + n - 1) // 2
14    class Range:
15        def __getitem__(self, i):
16            return after-i-1 < 0 or a[i] >= b[after-i-1]
17    i = bisect.bisect_left(Range(), True, 0, m)
18    nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
19    return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2
python

Conclusion

In this guide, we have learned more iterable Python tricks, such as map/reduce, pack/unpack, and the advanced skills for some built-in functions. I hope some of them will be useful for you.

There are other advanced techniques not mentioned here. This guide simply offers a good starting point to travel in the Python world. You can also download an example notebook, iterables.ipynb, from Github.

This guide is one of a series of Python tricks guides:

I hope you enjoyed it. If you have any questions, you're welcome to contact me at [email protected].