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