Python itertools

Python的内置库itertools是专门提供迭代器（iterator）和相关函数的库，虽然说Python3里面把一些迭代器从itertools库里面拿出来了，不过itertools库里还是有一些非常好用的函数。总览：

image.png

由于函数较多，挑一些用的多的，而自己实现比较麻烦的。这不代表其他函数没有用，只不过可以比较轻松地自己写一小段代码实现需要的功能，所以记住更好，记不住也没事。

1. accumulate(iterable [,func])
   阶梯累积功能的迭代器，默认的是求阶梯累加和，可以自定义函数：

>>> list(itertools.accumulate([1,2,3],lambda x,y: x*y))
[1, 2, 6]

注意和reduce函数区分开来，reduce是依次调用函数，对所有元素调用，而且函数是必要参数；这个是累积调用。当然，这个迭代器的最后一项，其实就是reduce的效果。字符串也可以作为参数：

 >>> list(itertools.accumulate('123'))
['1', '12', '123']  

2. groupby(iterable [,keyfunc])
   分组功能的函数，某些时候比较方便。

>>> (itertools.groupby(['my', 'oh', 'a'], len))
<itertools.groupby object at 0x013EB750> 
>>> list(itertools.groupby(['my', 'oh', 'a'], len))
[(2, <itertools._grouper object at 0x013E8530>), (1, <itertools._grouper object at 0x013E8550>)] 
>>> for le, it in (itertools.groupby(['my', 'oh', 'a'], len)):
 for i in it:
 print(le,i)

 
2 my
2 oh
1 a

可以看见，结果是两层迭代器，第一层(i, iter)是分组的函数结果和对应的迭代器，第二层是分组的内容。

3. zip_longest(p,q,fillvalue)
   现在zip函数就是只取两者最短的长度，所以这个zip_longest还是有用。默认用None填充，可以指定。

>>> list(zip('abc','1234'))
[('a', '1'), ('b', '2'), ('c', '3')]
 >>> list(itertools.zip_longest('abc','1234'))
[('a', '1'), ('b', '2'), ('c', '3'), (None, '4')]  

4. product(p,q [,repeat=1])
   不知道要怎么翻译。相当于嵌套for，用repeat相当于重复n次。product(A,B)相当于((x,y) for x in A for y in B)，还可以接受更多的参数。product(A, repeat=4) 则相当于product(A, A, A, A)。如果用了repeat，就只能接受一个迭代参数了。

5. permutations(p [,r])
   求排列，r可以指定长度。这个函数并不会自己识别有没有重复的字母。

>>> list(itertools.permutations('ABB'))
[('A', 'B', 'B'), ('A', 'B', 'B'), ('B', 'A', 'B'), ('B', 'B', 'A'), ('B', 'A', 'B'), ('B', 'B', 'A')]
>>> list(itertools.permutations('ABC',2))
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

6. combinations/combinations_with_replacement(p, r)
   求组合，r还是长度，前者不会重复使用，后者会。例子在图片里面已经给出了。

实际应用：例1. 给出一个升序的无重复正整数序列，将其转换为范围表示。比如[0,1,2,4,5,7]，返回["0->2","4->5","7"]。
【解】灵活利用各种工具库，可以得到很简洁漂亮的解法。这里其实有一个小规律，就是连续的区间，其值减去序号都是相等的，因为a,b相邻且连续，那么index自然加1，值也加1，相减抵消。因此可以巧妙地利用这一点，根据val-index的值使用groupby函数来分组。分组之后得到的是一个连续区间，或者单独一个数，可以用->符号连起来，这样单独的数就不会有->符号，然后处理一下多个数字的连续区间，比如10->11->12，把中间的->11->替换成为->即可，也就是解法中re库干的事情。

import re
import itertools
# Time:  O(n)
# Space: O(n)
class Solution:
    # @param{integer[]} nums
    # @return {string[]}
    def summaryRanges(self, nums):
        return [re.sub('->.*>', '->', '->'.join(str(n) for _, n in g))
            for _, g in itertools.groupby(enumerate(nums), lambda p: p[1] - p[0])]

例2. 给出一个字符串，返回其所有是回文字符串的组合。例如s='abab'，返回['abba', 'baab']。
【解】组合正好可以用permutations函数来求。不加思考的做法，就是对这个字符串求出所有组合，然后每一个判断是不是回文字符串。这样做效率太低。
更高效的做法是自己造回文字符串。回文字符串，长度无非奇数和偶数两种，也就是说，最多只能有一个字符的计数被2除余1。这个由对称性可以知道。因此，可以首先计数，假如不满足条件，直接就可以知道不能组成回文字符串。此外，假如有这么一个字符，那它只能在中间。然后，其余的字符拿出一半，在左边求组合，逆序放到右边，这样就能组成回文字符串了。代码如下：

# Time:  O(n * n!)
# Space: O(n)
import collections
import itertools
class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        cnt = collections.Counter(s)
        mid = tuple(k for k, v in cnt.items() if v % 2)
        chars = ''.join(k * (v // 2) for k, v in cnt.items())
        return [''.join(half_palindrome + mid + half_palindrome[::-1]) \
   for half_palindrome in set(itertools.permutations(chars))] if len(mid) < 2 else []