Python的內(nèi)置庫itertools是專門提供迭代器（iterator）和相關(guān)函數(shù)的庫，雖然說Python3里面把一些迭代器從itertools庫里面拿出來了，不過itertools庫里還是有一些非常好用的函數(shù)。總覽：

image.png

由于函數(shù)較多，挑一些用的多的，而自己實(shí)現(xiàn)比較麻煩的。這不代表其他函數(shù)沒有用，只不過可以比較輕松地自己寫一小段代碼實(shí)現(xiàn)需要的功能，所以記住更好，記不住也沒事。

1. accumulate(iterable [,func])
   階梯累積功能的迭代器，默認(rèn)的是求階梯累加和，可以自定義函數(shù)：

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

注意和reduce函數(shù)區(qū)分開來，reduce是依次調(diào)用函數(shù)，對所有元素調(diào)用，而且函數(shù)是必要參數(shù)；這個(gè)是累積調(diào)用。當(dāng)然，這個(gè)迭代器的最后一項(xiàng)，其實(shí)就是reduce的效果。字符串也可以作為參數(shù)：

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

2. groupby(iterable [,keyfunc])
   分組功能的函數(shù)，某些時(shí)候比較方便。

>>> (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

可以看見，結(jié)果是兩層迭代器，第一層(i, iter)是分組的函數(shù)結(jié)果和對應(yīng)的迭代器，第二層是分組的內(nèi)容。

3. zip_longest(p,q,fillvalue)
   現(xiàn)在zip函數(shù)就是只取兩者最短的長度，所以這個(gè)zip_longest還是有用。默認(rèn)用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])
   不知道要怎么翻譯。相當(dāng)于嵌套for，用repeat相當(dāng)于重復(fù)n次。product(A,B)相當(dāng)于((x,y) for x in A for y in B)，還可以接受更多的參數(shù)。product(A, repeat=4) 則相當(dāng)于product(A, A, A, A)。如果用了repeat，就只能接受一個(gè)迭代參數(shù)了。

5. permutations(p [,r])
   求排列，r可以指定長度。這個(gè)函數(shù)并不會(huì)自己識別有沒有重復(fù)的字母。

>>> 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還是長度，前者不會(huì)重復(fù)使用，后者會(huì)。例子在圖片里面已經(jīng)給出了。

實(shí)際應(yīng)用：例1. 給出一個(gè)升序的無重復(fù)正整數(shù)序列，將其轉(zhuǎn)換為范圍表示。比如[0,1,2,4,5,7]，返回["0->2","4->5","7"]。
【解】靈活利用各種工具庫，可以得到很簡潔漂亮的解法。這里其實(shí)有一個(gè)小規(guī)律，就是連續(xù)的區(qū)間，其值減去序號都是相等的，因?yàn)閍,b相鄰且連續(xù)，那么index自然加1，值也加1，相減抵消。因此可以巧妙地利用這一點(diǎn)，根據(jù)val-index的值使用groupby函數(shù)來分組。分組之后得到的是一個(gè)連續(xù)區(qū)間，或者單獨(dú)一個(gè)數(shù)，可以用->符號連起來，這樣單獨(dú)的數(shù)就不會(huì)有->符號，然后處理一下多個(gè)數(shù)字的連續(xù)區(qū)間，比如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. 給出一個(gè)字符串，返回其所有是回文字符串的組合。例如s='abab'，返回['abba', 'baab']。
【解】組合正好可以用permutations函數(shù)來求。不加思考的做法，就是對這個(gè)字符串求出所有組合，然后每一個(gè)判斷是不是回文字符串。這樣做效率太低。
更高效的做法是自己造回文字符串?；匚淖址L度無非奇數(shù)和偶數(shù)兩種，也就是說，最多只能有一個(gè)字符的計(jì)數(shù)被2除余1。這個(gè)由對稱性可以知道。因此，可以首先計(jì)數(shù)，假如不滿足條件，直接就可以知道不能組成回文字符串。此外，假如有這么一個(gè)字符，那它只能在中間。然后，其余的字符拿出一半，在左邊求組合，逆序放到右邊，這樣就能組成回文字符串了。代碼如下：

# 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 []