itertools应用之一

在上一篇文章中（《迭代器案例1：zip》中，已经使用过了 Python 标准库itertools，本文将继续探讨这个标准库中的几个有意思的函数，从而理解迭代器的应用。

组合与排列

数学中的“组合”与“排列”，如果用程序来实现，使用Python中的itertools模块的函数，是非常简单实用的。单纯来讲排列组合问题，没有什么意思，可以看一个经典的问题。

题目：假设有这样一些RMB：3张20元；5张10元；2张5元；5张1元。问：如何组合出100元。

首先，可以用一个列表，把已知的RMB表示出来。

rmb =  [20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1]
复制代码

刚才这个问题，是一个组合问题，比如，可以这么思考：先找出一张20的，然后逐个尝试，其它各种组合可能，直到找到和为100为止。这样就得到了一种组合方式。

Python标准库中的itertools就为我们提供了这样一个函数，实现这种组合。

>>> import itertools
>>> com = itertools.combinations([1,2,3], 2)
>>> list(com)
[(1, 2), (1, 3), (2, 3)]
复制代码

itertools.combinations([1,2,3], 2) 中的第一个参数是待组合的对象，第二个参数是组合结果中的元素个数。如果把这个函数用于 rmb 这个列表，就是这样的结果：

>>> list(itertools.combinations(rmb, 3))
[(20, 20, 20), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 5), (20, 20, 5), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 5), (20, 20, 5), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 5, 5), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 10), (20, 20, 5), (20, 20, 5), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 20, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 5, 5), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 10), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 5), (20, 10, 5), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 10, 1), (20, 5, 5), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 5, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (20, 1, 1), (10, 10, 10), (10, 10, 10), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 10), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 10, 10), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 10, 10), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 10, 5), (10, 10, 5), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 10, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 5, 5), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 5, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (10, 1, 1), (5, 5, 1), (5, 5, 1), (5, 5, 1), (5, 5, 1), (5, 5, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (5, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]
复制代码

然后，就从这些组合中挑出那些能够符合某些条件的，就是本问题的解了。不过，上面仅仅以组合3个元素为例。实际上可能是从1开始一直到rmb列表的长度为止。当然，我们一眼就可以看出来，只取得1个、2个，无论怎么组合，也达不到100。或者说，先从我们的分析角度出发考虑，最小的可能组合应该是（20, 20, 20, 10, 10, 10, 10），即至少要有7张钞票才能组合出100元。

>>> makes_100 = []
>>> for n in range(7, len(rmb)+1):
...     for comb in itertools.combinations(rmb, n):
...         if sum(comb) == 100:
...             makes_100.append(comb)
...
复制代码

注意，这时候得到的 makes_100 ，并不是最终结果。因为里面有很多重复的，之所以这样，是因为 rmb 中的元素就有重复的。所以，还要进一步去重。

>>> set(makes_100)
{(20, 20, 20, 10, 10, 10, 5, 5), (20, 20, 20, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 10, 10, 10, 10, 10, 5, 5), (20, 20, 10, 10, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 20, 10, 10, 10, 10)}
复制代码

得到了最终结果，可以有5中组合方案，实现100元的目标。

按照Python的编程习惯，上面的程序可以写成：

>>> makes_100 = [comb for n in range(7, len(rmb)+1) for comb in itertools.combinations(rmb, n)  if sum(comb)==100]
>>> set(makes_100)
{(20, 20, 20, 10, 10, 10, 5, 5), (20, 20, 20, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 10, 10, 10, 10, 10, 5, 5), (20, 20, 10, 10, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 20, 10, 10, 10, 10)}
复制代码

是不是显示出了Python的简洁。

这个问题还可以这样变化一下：

题目：有若干张面额为50、20、10、5、1元的RMB，问有多少种方式，能够组合出100元。

问题变化了，所用函数也要变化。因为 combinations() 的作用是从已知数据集中选择若干个元素组合，但是，并不会实现如本题中所要求的。例如问题中最直接的一种组合就是100个1元的。而这种组合是 combinations 函数无法提供的。

itertools中还有另外一个函数，它能帮助我们解决这个问题。

>>> list(itertools.combinations_with_replacement([1, 2], 2))
[(1, 1), (1, 2), (2, 2)]
>>> list(itertools.combinations([1,2], 2))    #注意比较两者的结果
[(1, 2)]
复制代码

从上述操作中，就可以看出 combinations_with_replacement 与 combinations 的区别了。 combinations_with_replacement 就是用来解决这个问题的函数。

>>> rmbs = [50, 20, 10, 5, 1]
>>> makes_100_2 = []
>>> for n in range(2, 101):
...     for comb in itertools.combinations_with_replacement(rmbs, n):
...         if sum(comb) == 100:
...             makes_100_2.append(comb)
...
#开始执行上面的程序，需要一段时间，你可以此时完成如下活动：喝水、上厕所、想想人生。
>>> len(makes_100_2)
343
复制代码

尽管上面的程序比较耗费时间，毕竟能够用暴力的方式解决了上述问题——需要执行96,560,645此组合。

对于“钱币组合”问题，是算法中的一个经典问题，在这里我们其实使用了“暴力穷举”的方法，不算是最好的方法，只是演示itertools中的两个函数的使用方法。

在itertools中，除了提供上述实现组合的函数之外，还提供了实现排列功能的函数： permutations()

>>> import itertools
>>> list(itertools.permutations(['a', 'b', 'c']))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
复制代码

数列

itertools 模块中，还提供了生成包含无限项的迭代器对象——注意，虽然说包含了无限项，但是因为它们并没有被读入内存，所以不用担心。这就是迭代器的优势。

奇数和偶数

从数学的角度来说，奇数和偶数，都有无限项。那么，在Python中如何表示这样的集合？这就要创建一个迭代器——其实下面所创建是生成器，生成器也是迭代器。

>>> def evens():
...     n = 0
...     while True:
...         yield n
...         n += 2
...
复制代码

这个函数，就能够生成偶数集合，它其实是返回了一个生成器对象——《跟老齐学Python：轻松入门》中有对生成器的详细讲述。

>>> e = evens()    #①
>>> list(next(e) for _ in range(6))    #②
[0, 2, 4, 6, 8, 10]
复制代码

①得到了偶数集合的生成器对象，在②中，通过循环语句，生成6个偶数，这时候，这些偶数才被读入内存。

同样的道理，奇数的生成器函数，也是类似的。

>>> def odds():
...     n = 1
...     while True:
...         yield n
...         n += 2
...
复制代码

无限多个数

在itertools中，还提供了另外一个函数，实现对某种特定规律的数的集合的迭代器对象的创建。

例如自然数：

>>> counter = itertools.count()
>>> list(next(counter) for _ in range(9))
[0, 1, 2, 3, 4, 5, 6, 7, 8]
复制代码

跟前面偶数和奇数集合的生成器对象类似，这里得到的 counter 对象也是只有在读取数值的时候，才根据设定的个数将相应的自然数读入内存——0是不是自然数？这里姑且认为是吧。

如果使用 help() 查看这个函数的帮助信息，可以看到这种表述：

count(start=0, step=1) --> count object

在 counter = itertools.count() 中没有设置参数 step 的值，意味着采用了默认的 step=1 ，并且另外一个参数 start=0 。从这两个参数的设置可知，我们可以设置从某个数值开始直到无限大，且步骤为某个值的自然数集合。那么前面演示过的偶数和奇数集合，就有另外一种方式实现了。

#偶数的迭代器
>>> evens = itertools.count(step=2)
>>> list(next(evens) for _ in range(9))
[0, 2, 4, 6, 8, 10, 12, 14, 16]

#奇数的迭代器
>>> odds = itertools.count(start=1, step=2)
>>> list(next(odds) for _ in range(9))
[1, 3, 5, 7, 9, 11, 13, 15, 17]
复制代码

其实，不仅可以针对自然数，还可以针对浮点数进行操作。注意：要Python3.1之后的版本。

>>> counter_float = itertools.count(start=0.5, step=0.25)
>>> list(next(counter_float) for _ in range(9))
[0.5, 0.75, 1.0, 1.25, 1.5, 1.75, 2.0, 2.25, 2.5]
复制代码

负数也可以。

>>> counter_negative = itertools.count(start=-1, step=-0.3)
>>> list(next(counter_negative) for _ in range(9))
[-1, -1.3, -1.6, -1.9000000000000001, -2.2, -2.5, -2.8, -3.0999999999999996, -3.3999999999999995]
复制代码

上面的结果中出现了一些特别的浮点数，这是什么原因——这个问题我早就在《跟老齐学Python：轻松入门》一书中讲得很清楚了，欲知详情，请参考。

通过上述操作， itertools.count() 和 range() 的区别也非常明显了。在针对自然数部分，两者功能类似，并且 range 也返回迭代器对象。但是， range 返回的对象都是在有限范围之内， count 则是无限的。另外的差别在于， count 不仅可以处理自然数范围的数字，还能处理负数、浮点数。

前面提到了生成器，虽然说有无限个数的集合有很多，并且前面列举了几个，多数通过 itertools.count 可以实现，对于它不能实现的，还可以写一个生成器（迭代器）函数来实现。下面这个例子，是在这时候一定要举出来的，那就是编写斐波那契数列的生成器函数——关于斐波那契数列的其它更多写法，推荐阅读拙作《跟老齐学Python：轻松入门》。

>>> def fibs():
...     a, b = 0, 1
...     while True:
...         yield a
...         a, b = b, a + b
...
复制代码

无限多项的斐波那契数列，就可以通过这个生成器函数获得。

>>> f = fibs()
>>> list(next(f) for _ in range(9))
[0, 1, 1, 2, 3, 5, 8, 13, 21]
复制代码

得到了9项斐波那契数列。

对于无限项的集合，要取出其部分有限个数的数字，除了用上面的循环方式 next(f) for _ in range(9) 之外，还可以使用itertools中的一个函数。例如：

>>> counter = itertools.count()
>>> list(itertools.islice(counter, 9))
[0, 1, 2, 3, 4, 5, 6, 7, 8]
复制代码

itertools真不辜负它的名字。

递推关系式

在数学中， 递归 或者 递推关系 （ recurrence relation）在数列中常见，比如等差数列、等比数列等，都是递归关系式。从这点上来看，前面使用 itertools.count 得到的数列，都是一种递归关系的数列。

前面列举的斐波那契数列数列，其实也是一些具有递归关系的数。或者说，也可以通过“递归”实现斐波那契数列函数。

不过，还有一种递归关系的数列，不能用 itertools.count 得到，那就是所有的数字都是一样的，比如都是由1组成的，或者是由某几个数字组成，比如都是由1，3，5组成。

对此，itertools模块提供了别的函数。

>>> ones = itertools.repeat(1)
>>> list(itertools.islice(ones, 9))
[1, 1, 1, 1, 1, 1, 1, 1, 1]
复制代码

itertools.repeat 函数专门生成由某个数字组成的无限长数列。注意：其参数除了数字之外，还可以是其它对象，比如字符串、列表等。

当然，创建有限的也可以，那就增加一个标识元素个数的参数。

>>> five_ones = itertools.repeat(1, 5)
>>> [i for i in five_ones]
[1, 1, 1, 1, 1]
复制代码

另外一种情况，则可以使用 itertools.cycle 函数实现。先不用看示例演示，看函数名称，就能猜测到结果应该是什么样子的——[1,3,5,1,3,5,...]，应该如此，否则就不能是cycle了。

>>> otf = itertools.cycle([1, 3, 5])
>>> list(itertools.islice(otf, 9))
[1, 3, 5, 1, 3, 5, 1, 3, 5, 1, 3, 5, 1, 3, 5]
复制代码

上面的演示中，只取出数列的前15项看看，果然不出所料。

以上演示的都是递推关系中的特例，下面要用数学形式说明一下递推关系中的所谓一阶和二阶递推关系。

数列中相邻两项符合此式子的，就是一阶递归关系数列。

• P=1，为等差数列
• P=1，且h=0，为常数列
• P≠0，且h=0，为等比数列。

还有另外一种递推关系，它表示的是某一项和相邻的两项之间的关系，比如前面的斐波那契数列，第三项等于前两项和。这种关系的通项式可以表示为：

对于此通项式，如果P=Q=1，且h=0，那么它就称为了斐波那契数列。

如果根据上述通项式，可知前面用 count 、 repeat 、 cycle 等所实现的数列，都是特殊数列。有没有比它们更一般的呢？

必须有。

>>> list(range(9))
[0, 1, 2, 3, 4, 5, 6, 7, 8]
>>> list(itertools.accumulate(range(9)))
[0, 1, 3, 6, 10, 15, 21, 28, 36]
复制代码

注意，上面实现的不是斐波那契数列，而是按照下图所示方式得到了一个新的数列。

看到这个函数，你应该想起来另外一个函数，如果没有想起来，说明你的基础知识尚有发展的空间。

>>> import functools
>>> functools.reduce(lambda x,y :x+y, range(9))
36
复制代码

与 functools.reduce 相比， itertools.accumulate 返回的不是一个数，而是数列，如果严格地说，是由数列元素作为潜在对象的迭代器对象。

已经看到了 itertools.accumulate(range(9)) 的结果了。而对于 accumulate() 而言，其完整的参数形式是这样的：

accumulate(iterable[, func]) --> accumulate object

默认情况，后面的func是加法函数。所以，像下面的方式与前述示例是一样的。

>>> import operator
>>> list(itertools.accumulate(range(9), operator.add))
[0, 1, 3, 6, 10, 15, 21, 28, 36]
复制代码

根据这个原理，就可以对很多数列进行操作，依据函数关系得到另外一个数列了。下面依次列举若干示例。

>>> list(itertools.accumulate([9, 21, 17, 5, 11, 12, 2, 6], min))
[9, 9, 9, 5, 5, 5, 2, 2]

>>> list(itertools.accumulate([1, 2, 3, 4, 5], lambda x, y: (x + y) / 2))
[1, 1.5, 2.25, 3.125, 4.0625]
复制代码

还记得前面的一阶递归关系式吗？如果写一个函数，实现那个关系式？

>>> def first_order(p, h, initial_val):
...     return itertools.accumulate(itertools.repeat(initial_val), lambda a, _: p*a + h)
...
复制代码

这个函数就是一阶递归通项式，通过它能够得到一阶递归的数列。

在函数中综合运用了学习过的两个函数。下面测试一下。

>>> evens = first_order(p=1, h=2, initial_val=0)    #得到偶数数列
>>> list(itertools.islice(evens, 5))
[0, 2, 4, 6, 8]

#能被3整除的数
>>> count_by_threes = first_order(p=1, h=3, initial_val=0)
>>> list(itertools.islice(count_by_threes, 5))
[0, 3, 6, 9, 12]

#由1，-1组成的数列
>>> alternating_ones = first_order(p=-1, h=0, initial_val=1)
>>> list(itertools.islice(alternating_ones, 5))
[1, -1, 1, -1, 1]

#都是1组成的数列
>>> all_ones = first_order(p=1, h=0, initial_val=1)
>>> list(itertools.islice(all_ones, 5))
[1, 1, 1, 1, 1]
复制代码

通过上面的示例不难看出，当得到了一阶递推关系式通项之后，所有一阶递推数列，都可以通吃了。

厉害。

同样，也可以写出二阶递归关系的通项函数。

>>> def second_order(p, q, h, initial_val):
...     itermediate = itertools.accumulate(
                              itertools.repeat(initial_val), 
                              lambda a, _:(a[1], p*a[1] + q*a[0] + h))
...     return map(lambda x: x[0], itermediate)
...
复制代码

二阶递归关系通项函数貌似复杂。因为二阶递推通项式中，初始值是前两项，所以，如果直接实现数学函数值，返回的是两个值，就不得不使用 map 函数，把其中的值一个一个取出来。

写好之后，用它来生成斐波那契数列。

>>> fibs = second_order(p=1, q=1, h=0, initial_val=(0, 1))
>>> list(itertools.islice(fibs, 9))
[0, 1, 1, 2, 3, 5, 8, 13, 21]
复制代码

对照前面斐波那契数列数列。感受到二阶递推关系的通项函数魅力了吧。

典型的二阶递推关系除了斐波那契数列之外，还有佩尔数（Pell number）和卢卡斯数（Lucas number）。

Pell number:

Lucas Number:

下面就用上面的二阶递推关系通项实现这两个数列。

>>> pell = second_order(p=2, q=1, h=0, initial_val=(0, 1))
>>> list(itertools.islice(pell, 6))
[0, 1, 2, 5, 12, 29]

>>> lucas = second_order(p=1, q=1, h=0, initial_val=(2, 1))
>>> list(itertools.islice(lucas, 6))
[2, 1, 3, 4, 7, 11]
复制代码

迭代器的确是个好东西，itertools还有更多好内容。

系列图书：

• 《跟老齐学Python：轻松入门》：面向Python语言入门学习者，本书基于Python3.x
• 《跟老齐学Python：Django实战》：面向学习Web开发的读者，本书的第一版是基于Django1.10，第二版基于Django2.x
• 《跟老齐学Python：数据分析》：面向数据科学（数据分析、机器学习）的入门学习者