• Source 
    1. # -*- coding: utf-8 -*-
    2. # q1038_answer_2.py
    3.  
    4. # 使用した Python のバージョン：
    5. # ・Python(Python 2.7.2)/Python3(Python 3.2.3)
    6. # 工夫した点・苦労した点・感想等（ご自由にお書きください）：
    7. # ・infinite_product_process 関数で得られる generator をキューに登録して順次実行する仕組みにしました。
    8. # ・infinite_product 関数の最初で、Iterator のクローンを返す関数を返す内部関数 iterator_cloner を定義しています。
    9. # ・infinite_product 関数でその後、引数 iters を iterator_cloner 関数に渡して以降はその結果を利用しています。
    10. # ・infinite_product_process 関数は、今までに列挙した値と、列挙に使わなかった残りの cloners を引数にとって、
    11. # 　そのうちの先頭の cloner から取得した Iterator（generator）で値を列挙してその値と cloners の残りを yield に引き渡しています。
    12.  
    13. # 必要に応じてここに import 文を挿入してもOKです（標準添付ライブラリに限る）。
    14. # 例：import itertools
    15. from collections import deque
    16.  
    17. # 無限リスト（ストリーム）に対応した直積（Cartesian product）を生成して列挙する関数（generator 関数）
    18. def infinite_product(*iters):
    19.     """Cartesian product generator function of (infinite) iterables."""
    20.  
    21.     def iterator_cloner(it):
    22.         _it = iter(it)
    23.         _cache = []
    24.         def _gen(_it=_it, _cache=_cache):
    25.             index = 0
    26.             while True:
    27.                 if len(_cache) <= index:
    28.                     next_val = next(_it)
    29.                     _cache.append(next_val)
    30.                 yield _cache[index]
    31.                 index += 1
    32.         return _gen
    33.  
    34.     q = deque([infinite_product_process((), [iterator_cloner(it) for it in iters])])
    35.     while q:
    36.         it = q.popleft()
    37.         try:
    38.             vals, next_cloners = next(it)
    39.             if not next_cloners:
    40.                 yield vals
    41.             else:
    42.                 q.append(infinite_product_process(vals, next_cloners))
    43.             q.append(it)
    44.         except StopIteration:
    45.             pass
    46.  
    47.  
    48. def infinite_product_process(vals, cloners):
    49.     """Sub-generator function for infinite_product()."""
    50.     if not cloners:
    51.         yield vals, ()
    52.         return
    53.  
    54.     it = cloners[0]()
    55.     xs = cloners[1:]
    56.     for e in it:
    57.         yield (vals + (e,), xs)
    58.  
    59.  
    60. # ここに Lv.2 問題で作成した IteratorCloner クラスを転記してください。
    61. # ※利用せずに解けた場合は、ここには何も記述しないでください。
    62. # ※Lv.2 問題に挑戦していない方は、ここには何も記述せず上記2関数内で完結するようがんばって実装してください。
    63. # v--ココカラ
    64.  
    65.  
    66. # ^--ココマデ
    67.  
    68. # ※これ以降は変更しないこと。
    69. if __name__ == '__main__':
    70.     import unittest
    71.     from itertools import count, islice
    72.     try:
    73.         # for Python2
    74.         from itertools import ifilter
    75.     except ImportError:
    76.         # for Python3
    77.         ifilter = filter
    78.  
    79.  
    80.     def primes():
    81.         """Generator function of Prime numbers."""
    82.         g = count(2)
    83.         while True:
    84.             prime = next(g)
    85.             yield prime
    86.             g = ifilter(lambda x, prime=prime: x%prime, g)
    87.  
    88.  
    89.     def nats():
    90.         """Generator function of Integers(>0)."""
    91.         return count(1)
    92.  
    93.  
    94.     def fib():
    95.         """Generator function of Fibonacci numbers."""
    96.         a, b = 0, 1
    97.         while True:
    98.             yield b
    99.             a, b = b, a + b
    100.  
    101.  
    102.     class Q99Test(unittest.TestCase):
    103.         """Test class for infinite_product()."""
    104.  
    105.         def test_fib_only(self):
    106.             """Test for Fibonacci numbers."""
    107.             expected = [(1,), (1,), (2,), (3,), (5,), (8,), (13,), (21,), (34,), (55,)]
    108.             result = list(islice(infinite_product(fib()), 10))
    109.             self.assertEqual(result, expected)
    110.  
    111.  
    112.         def test_product_nats_fib(self):
    113.             """Test for product of Integers(>0) and Fibonacci numbers."""
    114.             expected = [
    115.                 (1, 1),
    116.                 (1, 1), (2, 1),
    117.                 (1, 2), (2, 1), (3, 1),
    118.                 (1, 3), (2, 2), (3, 1), (4, 1),
    119.                 (1, 5), (2, 3), (3, 2), (4, 1), (5, 1),
    120.                 (1, 8), (2, 5), (3, 3), (4, 2), (5, 1), (6, 1)
    121.             ]
    122.             result = list(islice(infinite_product(nats(), fib()), 21))
    123.             self.assertEqual(result, expected)
    124.  
    125.  
    126.         def test_product_primes_nats_fib(self):
    127.             """Test for product of Primes and Integers(>0) and Fibonacci numbers."""
    128.             expected = [
    129.                 (2, 1, 1),
    130.                 (2, 1, 1), (2, 2, 1),
    131.                 (3, 1, 1),
    132.                 (2, 1, 2), (2, 2, 1), (2, 3, 1),
    133.                 (3, 1, 1), (3, 2, 1),
    134.                 (5, 1, 1),
    135.                 (2, 1, 3), (2, 2, 2), (2, 3, 1), (2, 4, 1),
    136.                 (3, 1, 2), (3, 2, 1), (3, 3, 1),
    137.                 (5, 1, 1), (5, 2, 1),
    138.                 (7, 1, 1),
    139.                 (2, 1, 5), (2, 2, 3), (2, 3, 2), (2, 4, 1), (2, 5, 1),
    140.                 (3, 1, 3), (3, 2, 2), (3, 3, 1), (3, 4, 1),
    141.                 (5, 1, 2), (5, 2, 1), (5, 3, 1),
    142.                 (7, 1, 1), (7, 2, 1),
    143.                 (11, 1, 1)
    144.             ]
    145.             result = list(islice(infinite_product(primes(), nats(), fib()), 35))
    146.             self.assertEqual(result, expected)
    147.  
    148.  
    149.         def test_product_nats_1_3(self):
    150.             """Test for product of Integers(>0) and [1, 2, 3]."""
    151.             expected = [
    152.                 (1, 1),
    153.                 (1, 2), (2, 1),
    154.                 (1, 3), (2, 2), (3, 1),
    155.                         (2, 3), (3, 2), (4, 1),
    156.                                 (3, 3), (4, 2), (5, 1),
    157.                                         (4, 3), (5, 2), (6, 1)
    158.             ]
    159.             result = list(islice(infinite_product(nats(), range(1, 4)), 15))
    160.             self.assertEqual(result, expected)
    161.  
    162.  
    163.         def test_product_1_3_nats(self):
    164.             """Test for product of [1, 2, 3] and Integers(>0)."""
    165.             expected = [
    166.                 (1, 1),
    167.                 (1, 2), (2, 1),
    168.                 (1, 3), (2, 2), (3, 1),
    169.                 (1, 4), (2, 3), (3, 2),
    170.                 (1, 5), (2, 4), (3, 3),
    171.                 (1, 6), (2, 5), (3, 4)
    172.             ]
    173.             result = list(islice(infinite_product(range(1, 4), nats()), 15))
    174.             self.assertEqual(result, expected)
    175.  
    176.  
    177.         def test_product_1_2_x3(self):
    178.             """Test [1, 2] x 3"""
    179.             expected = [
    180.                 (1, 1, 1),
    181.                 (1, 1, 2), (1, 2, 1), (2, 1, 1),
    182.                 (1, 2, 2), (2, 1, 2), (2, 2, 1),
    183.                 (2, 2, 2)
    184.             ]
    185.             # result = list(islice(infinite_product([1, 2], [1, 2], [1, 2]), 8))
    186.             result = list(infinite_product([1, 2], [1, 2], [1, 2]))
    187.             self.assertEqual(result, expected)
    188.  
    189.  
    190.         def test_product_1_2_x4(self):
    191.             """Test [1, 2] x 4"""
    192.             expected = [
    193.                 (1, 1, 1, 1),
    194.                 (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1),
    195.                 (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1),
    196.                 (1, 2, 2, 2), (2, 1, 2, 2), (2, 2, 1, 2), (2, 2, 2, 1),
    197.                 (2, 2, 2, 2)
    198.             ]
    199.             # result = list(islice(infinite_product([1, 2], [1, 2], [1, 2], [1, 2]), 16))
    200.             result = list(infinite_product([1, 2], [1, 2], [1, 2], [1, 2]))
    201.             self.assertEqual(result, expected)
    202.  
    203.  
    204.     # run tests
    205.     unittest.main()
    206.