「yieldのお勉強 Lv.99」解説（Ruby編/Python編共通） #CodeIQ

先日、CodeIQ の以下の問題が、公開終了となりました。
たくさんの挑戦、ありがとうございます。

• yieldのお勉強 Lv.99 （Ruby編）（ https://codeiq.jp/ace/antimon2/q1037 ）
• yieldのお勉強 Lv.99 （Ruby編）（ https://codeiq.jp/ace/antimon2/q1038 ）

（すでに問題の公開は終了していますので、上記 URL で問題詳細を見ることはできません）

ということで、恒例の解説記事です。
今回は個人的事情*1で解説が遅れましてスミマセン。

いつものように問題文は省略します（挑戦者だけの特典♪）が、Lv.1/Lv.2 と同様、問題は、一部が未実装のプログラムを実装してテストを全て通るようにする、というもの。
以下に、問題プログラム・解説、そして解答例を示します。

なお、一部前回の ヒント記事 にて既に部分解説している情報もあります。必要に応じてそちらも参照してください。

問題プログラム

まずは問題プログラムを再掲します。

問題プログラム（Ruby編）：

問題プログラム（Python編）：

問題は、「引数で与えられた複数のイテレータの直積を列挙*2する関数（メソッド）を実装する」というもの。
ただし、引数に所謂「無限リスト（ストリーム）」が与えられた場合にも対応すること。
また「無限リスト（ストリーム）」に対応する直積（の要素の列挙方法）はいくつかやり方があるのですが、それを、列挙される順番をテストコードで示すことによって指定しています。
「ここで示した順番で列挙されるように実装すること」という条件も含まれている、ということです。

列挙順序についての詳しい解説は、前回の ヒント記事 を参照してください。

今回は、私の解答例を示す前に、挑戦者のみなさまから寄せられた解答の総評と傾向から述べていきます。

の、前に、先に反省点

今回も、テストケースが足りなかったのは反省点です(>_<)
ただし、ある特定の場合を除いてはきちんとこちらの意図した通りの動きをする解答が寄せられてきたので、一安心。
でも、こちらの本来意図していたその「特定のケース」まで含めて、一発で応えてくれた挑戦者さまは、ごくわずかでした。

その特定のケースとは、テストケースで言うと以下の2点（Pythonのテストケースで示しておきます）：

        def test_product_1_2_x3(self):
            """Test [1, 2] x 3"""
            expected = [
                (1, 1, 1),
                (1, 1, 2), (1, 2, 1), (2, 1, 1),
                (1, 2, 2), (2, 1, 2), (2, 2, 1),
                (2, 2, 2)
            ]
            result = list(infinite_product([1, 2], [1, 2], [1, 2]))
            self.assertEqual(result, expected)


        def test_product_1_2_x4(self):
            """Test [1, 2] x 4"""
            expected = [
                (1, 1, 1, 1),
                (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1),
                (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1),
                (1, 2, 2, 2), (2, 1, 2, 2), (2, 2, 1, 2), (2, 2, 2, 1),
                (2, 2, 2, 2)
            ]
            result = list(infinite_product([1, 2], [1, 2], [1, 2], [1, 2]))
            self.assertEqual(result, expected)

つまり。

• 引数が全て有限の iterable（イテレータ）の場合。
• 引数が4つ以上の場合。

特に前者。上記のテストケースを追加すると、無限ループに陥って返ってこない解答が続出でした(>_<)

ちなみにこの2つのテストケースを問題プログラムに入れなかったのは（言い訳ですが）、そのままテストケースを入れてしまうと、問題プログラムが無限ループに陥って ideone.com が時間制限で落ちてしまうからです。
でも、コメントアウトした状態で入れておいて、
「他のテストケースが通るようになったらこれらのコメントアウトも外してね」
という形にしておくべきだったかなー、と問題掲載後2週間くらいで気付きました。
後悔先に立たず、ですね(_ _;

なお、今回も正解の必要条件は「用意したテストケースを全てパスすること」であり、この「特定のケース」が満たされなくても正解として扱っています*3。
一方でこの特定のケースも含めて正解である場合を『真の正解』と呼ばせていただきます。

解答の傾向と総評

今回は、1つだけではなく、2つの関数（メソッド）を実装する問題となっておりました。
しかも、両方とも yield を使用する、という制約条件を付与していました。
問題プログラム中にもコメントしてある通り、その2つの関数（メソッド）*4の使い分け、特に「infinite_product_process() 関数」をどう扱うか、がポイントになっています。

実際、寄せられた解答を見てみると、この「infinite_product_process() 関数」をどう扱っているかで、解答が大きく以下のように分類分けされました。

1. 必要な各次元の要素を再帰で探索して列挙する方法
   • →呼び出し側である infinite_product() は、その結果を単純に yield するだけのことが多い。
2. 要素をレベル（もしくは段； ヒント記事 で示したあの「斜め」のグループ）ごとにすべての要素を列挙する方法
   • →呼び出し側である infinite_product() は、カウンターをループで回して↑を呼び、その結果を yield 。
3. 要素をレベル（もしくは段；同上）ごとに「列挙するインデックスの組合せ（つまりどのイテレータから何番目の要素を取得するか）」を列挙する方法
   • →呼び出し側である infinite_product() は、カウンターをループで回して↑を呼び、その結果から「yieldする組合せ」を生成して yield 。

後ろの2つは考え方はほぼ同じで、「実際に列挙する組合せ」を生成するのが「infinite_product_process()」側か「infinite_product()」側か、の違いです。

挑戦してくださった方はほぼ全員正解だったのですが、その中でも（先ほども言った）「特定のケース（こちらで用意していた追加のテストケース）」まで含めて一発で『真の正解』*5だった方は、Ruby編/Python編合わせて4名いらっしゃいました。

その中の、お一方のみ解答を紹介致します。

じゅんや様の解答（必要な箇所のみ抜粋）：

# 必要に応じてここに import 文を挿入してもOKです（標準添付ライブラリに限る）。
# 例：import itertools
from itertools import chain
try:
    # for Python2
    from itertools import izip_longest as zip_longest
except ImportError:
    # for Python3
    from itertools import zip_longest

# 無限リスト（ストリーム）に対応した直積（Cartesian product）を生成して列挙する関数（generator 関数）
def infinite_product(*iters):
    """Cartesian product generator function of (infinite) iterables."""
    # ここを適切に実装しなおしてテストが通るようにしてください。
    # ただし、以下の条件を満たすこと：
    # ・後述の別関数 infinite_product_process を利用すること。
    # ・yield 式を必ず利用すること。
    for product in chain.from_iterable(infinite_product_process(*iters)):
        yield product

    # 桜先生からのワンポイントアドバイス：
    # ・今まで学んだことを最大限に活かしてね♪
    # ・Good Luck!


def infinite_product_process(*iters):
    """Sub-generator function for infinite_product()."""
    # この関数の引数は変更しても可↑↑。
    # ここを適切に実装してテストが通るようにしてください。
    # ただし、以下の条件を満たすこと：
    # ・yield 式を必ず利用すること。
    # 桜先生からのワンポイントアドバイス：
    # ・この infinite_product_process 関数の使い方がポイント。
    # 　何を受け取って、何を返すか（何を yield 式に引き渡すのか）。
    # 　あと、何回呼び出すのか、どこから呼び出すのか、とかもね。
    # ・あとは、えーと…ぐ、Good Luck! 
    if len(iters) == 0:
        return
    try:
        iter(iters[0])
    except TypeError:
        it = [iters[0]]
    else:
        it = iters[0]
    
    if len(iters) == 1:
        for e in it:
            yield [(e,)]
    else:
        clone, sub_clone = [], []
        stop = object()
        for next_e, next_sub_list in zip_longest(it, infinite_product_process(*iters[1:]), fillvalue=stop):
            if next_e != stop:
                clone.append(next_e)
            if next_sub_list != stop:
                sub_clone.append(next_sub_list)
                
            yield [(e,)+sub_product
                for e, sub_list in zip(clone[-len(sub_clone):], reversed(sub_clone)) 
                for sub_product in sub_list]
        
        for i in range(1,min(len(clone),len(sub_clone))):
            yield [(e,)+sub_product
                for e, sub_list in zip(clone[-len(sub_clone):][i:], reversed(sub_clone[i:]))
                for sub_product in sub_list]
        
# ここに Lv.2 問題で作成した IteratorCloner クラスを転記してください。
# ※利用せずに解けた場合は、ここには何も記述しないでください。
# ※Lv.2 問題に挑戦していない方は、ここには何も記述せず上記2関数内で完結するようがんばって実装してください。
# v--ココカラ


# ^--ココマデ

先ほどの分類で言えば、1. の「再帰で全ての組合せを列挙」するパターンですが、単純にどんどん列挙して yield するのではなく、Python の標準添付ライブラリ itertools に用意されている数々の関数を駆使してうまく組み合わせ、キレイに仕様を満たす実装になっています。
『真の解答』一番乗りであり、かつ私の用意した解答例に一番近い解答でした。

ところで、私の用意していた解答例というのはどういうのかというと。
詳細は次節で解説しますが、先ほどの分類で言うと、実は、どのパターンにも当てはまりません！　全く異なるアプローチです。
それは次のような方法：

• infinite_product_process() は、「与えられたイテレータのどれか1つのみ値を列挙して、既に列挙済の（他の）イテレータの要素との組合せ（tuple）と、まだ列挙していないイテレータのリストを yield」する方法（再帰なし）
  • →呼び出し側である infinite_product() は、↑で生成したイテレータをキューに入れて順に処理しながら1つずつ値の組合せを yield する。

解答例と解説

ということでお待たせしました。解答例です。
なお以下の解答例には、先ほどの「特定のケース（追加のテストケース）」も含めてあります。

Ruby編 解答例：

Python編 解答例1（IteratorCloner クラスを Lv.2 問題のモノから転記したモノ）：

Python編 解答例2（IteratorCloner クラスを利用せず別関数を用意*6したモノ）：

infinite_product_process から解説します。
（Python編 解答例1より抜粋）

def infinite_product_process(vals, cloners):
    """Sub-generator function for infinite_product()."""
    if not cloners:
        yield vals, ()
        return

    it = cloners[0].get_clone()
    xs = cloners[1:]
    for e in it:
        yield (vals + (e,), xs)

• 最初の3行（Docstring より後）は、元の infinite_product の方で引数が1件も指定されなかった場合の保険です。
• 後ろの4行がメイン。引数 cloners（Ruby 編の解答例では iters）の先頭のイテレータ（のコピー）を取り出して、それを列挙しています。

なお、yield する値は、「『vals と列挙した新しい要素 e を結合した新しい tuple（Ruby では配列）』と、『残りのイテレータのリスト』からなる tuple（Rubyでは以下略）」です。

具体例（実行イメージ）を挙げます：

for t in infinite_product_process((2, 1), [《フィボナッチ数列を列挙するイテレータ（のCloner）》, it2, it3]):
    print(t)
    # => ((2, 1, 1), [it2, it3])
    # => ((2, 1, 1), [it2, it3])
    # => ((2, 1, 2), [it2, it3])
    # => ((2, 1, 3), [it2, it3])
    # => ((2, 1, 5), [it2, it3])
    # =>   : 《以下略》

これを利用する側、すなわち infinite_product の実装は、以下のようになっています（分かりやすいように行末に行番号をコメントで付加しました）。

def infinite_product(*iters):
    """Cartesian product generator function of (infinite) iterables."""
    q = deque([infinite_product_process((), [IteratorCloner(it) for it in iters])]) # L1
    while q:    # L2
        it = q.popleft()    # L3
        try:
            vals, next_cloners = next(it)   # L4
            if not next_cloners:    # L5
                yield vals  # L6
            else:
                q.append(infinite_product_process(vals, next_cloners))  # L7
            q.append(it)    # L8
        except StopIteration:
            pass    # L9

• [L1] まず最初に、引数 iters を全てまとめて、IteratorCloner で変換します。
  • ↑Ruby の場合は、#to_enum メソッドで Enumerator に変換します。
• [L1] 空の tuple（Ruby の場合は空の配列）と↑で変換したリストの組を infinite_product_process に渡し、その結果のイテレータ1つのみからなるキュー（Ruby の場合はただの配列）を生成します（変数 q）。
• [L2] q が空でない間、ループを回し以下を実行します：
  • [L3, L4] q からイテレータを取り出し、next() を利用して「次の組」を取り出します。
    • [L9] 取得に失敗したら、特に何もせずに次のループに処理を移します。
  • [L5, L6] 取得した組の後者（＝next_cloners）が空なら、得られた組の前者（＝vals）が列挙すべき値の組なので、そのまま yield します。
  • [L7] ↑そうでなければ、得られた vals と next_cloners の組を infinite_product_process に渡して新しいイテレータを生成し、それをキューに追加します。
  • [L8] 最後に、キューから取り出したイテレータを再びキューに追加します。

具体例、というか、実行イメージは、以下のようになります。
以下、(〜, 〜) は tuple 、[〜, 〜] はリスト、{〜, …} はイテレータを表します。

まずは分かりやすく、引数が fib() 1つだけの場合：

L1: q = [{((1,), []), …}]
L2: True（q is not empty）
L3: it = {((1,), []), …}, q = []
L4: vals = (1,), next_cloners = [], it = {((1,), []), …}
L5: True
L6: yield (1,)  # => (1,)
L8: q = [{((1,), []), …}]
L2: True（q is not empty）
L3: it = {((1,), []), …}, q = []
L4: vals = (1,), next_cloners = [], it = {((2,), []), …}
L5: True
L6: yield (1,)  # => (1,)
L8: q = [{((2,), []), …}]
L2: True（q is not empty）
L3: it = {((2,), []), …}, q = []
L4: vals = (2,), next_cloners = [], it = {((3,), []), …}
L5: True
L6: yield (2,)  # => (2,)
L8: q = [{((3,), []), …}]
L2: True（q is not empty）
L3: it = {((3,), []), …}, q = []
L4: vals = (3,), next_cloners = [], it = {((5,), []), …}
L5: True
L6: yield (3,)  # => (3,)
L8: q = [{((5,), []), …}]
  : 《以下同様に続く》

これは単純。
最初にキューにイテレータを格納した後は、毎回、キューから取り出して、次の値を取得して、キューに戻す、これの繰り返し。それだけです。

続いて、nats(), fib() を引数に渡した場合の実行例：

L1: q = [{((1,), [fib]), …}]
L2: True（q is not empty）
L3: it = {((1,), [fib]), …}, q = []
L4: vals = (1,), next_cloners = [fib], it = {((2,), [fib]), …}
L5: False
L7: q = [{((1, 1), []), …}]
L8: q = [{((1, 1), []), …}, {((2,), [fib]), …}]
L2: True（q is not empty）
L3: it = {((1, 1), []), …}, q = [{((2,), [fib]), …}]
L4: vals = (1, 1), next_cloners = [], it = {((1, 1), []), …}
L5: True
L6: yield (1, 1)    # => (1, 1)
L8: q = [{((2,), [fib]), …}, {((1, 1), []), …}]
L2: True（q is not empty）
L3: it = {((2,), [fib]), …}, q = [{((1, 1), []), …}]
L4: vals = (2,), next_cloners = [fib], it = {((3,), [fib]), …}
L5: False
L7: q = [{((1, 1), []), …}, {((2, 1), []), …}]
L8: q = [{((1, 1), []), …}, {((2, 1), []), …}, {((3,), [fib]), …}]
L2: True（q is not empty）
L3: it = {((1, 1), []), …}, q = [{((2, 1), []), …}, {((3,), [fib]), …}]
L4: vals = (1, 1), next_cloners = [], it = {((1, 2), []), …}
L5: True
L6: yield (1, 1)    # => (1, 1)
L8: q = [{((2, 1), []), …}, {((3,), [fib]), …}, {((1, 2), []), …}]
L2: True（q is not empty）
L3: it = {((2, 1), []), …}, q = [{((3,), [fib]), …}, {((1, 2), []), …}]
L4: vals = (2, 1), next_cloners = [], it = {((2, 1), []), …}
L5: True
L6: yield (2, 1)    # => (2, 1)
L8: q = [{((3,), [fib]), …}, {((1, 2), []), …}, {((2, 1), []), …}]
  : 《中略》
L6: yield (1, 2)    # => (1, 2)
L8: q = [{((2, 1), []), …}, {((3, 1), []), …}, {((4,), [fib]), …}, {((1, 3), []), …}]
  : 《中略》
L6: yield (2, 1)    # => (2, 1)
L8: q = [{((3, 1), []), …}, {((4,), [fib]), …}, {((1, 3), []), …}, {((2, 2), []), …}]
  : 《中略》
L6: yield (3, 1)    # => (3, 1)
L8: q = [{((4,), [fib]), …}, {((1, 3), []), …}, {((2, 2), []), …}, {((3, 1), []), …}]
  : 《中略》
L6: yield (1, 3)    # => (1, 3)
L8: q = [{((2, 2), []), …}, {((3, 1), []), …}, {((4, 1), []), …}, {((5,), [fib]), …}, {((1, 5), []), …}]
  : 《中略》
L6: yield (2, 2)    # => (2, 2)
L8: q = [{((3, 1), []), …}, {((4, 1), []), …}, {((5,), [fib]), …}, {((1, 5), []), …}, {((2, 3), []), …}]
  : 《中略》
L6: yield (3, 1)    # => (3, 1)
L8: q = [{((4, 1), []), …}, {((5,), [fib]), …}, {((1, 5), []), …}, {((2, 3), []), …}, {((3, 2), []), …}]
  : 《中略》
L6: yield (4, 1)    # => (4, 1)
L8: q = [{((5,), [fib]), …}, {((1, 5), []), …}, {((2, 3), []), …}, {((3, 2), []), …}, {((4, 1), []), …}]
  : 《以下略》

少し複雑ですが、キューから取り出したイテレータの扱い方は大きく分けて以下の2種類：

• vals が次元数（＝引数で与えられた iters の個数）に満たない場合は、infinite_product_process を呼んで得られたイテレータをキューに格納する。
• vals が次元数に等しい場合は、引数1個のときと同様に取得した vals（tuple）をそのまま yield する。

特に前者の処理でやってるのは、「『次に yield する値の組を生成するイテレータ』を生成」しています。
それをキューに入れて、順次処理することで、必要な値を適切な順序で取得して yield、を実現しています。
前回の ヒント記事 で述べた、以下に相当する処理です：

列挙のために必要なイテレータを、タイミングを見計らって1個ずつ新規生成します。
そのイテレータを、うまく並べて、1個ずつ『次の値』を取得して yield します。
これの繰り返し。

この実行イメージを、もう少しじっくり見てみてください。
先ほど述べた前者のイテレータ（＝vals が次元数に満たないイテレータ）が、うまいことセパレータの役割となって、q がそれらを挟んで列挙すべきものが順番に出現する1次元のキューになっているのが、お分かりになりますでしょうか？

さらに（もう少しお付き合いください）、primes(), nats(), fib() を引数に渡した場合の実行例！：

L1: q = [{((2,), [nats, fib]), …}]
L2: True（q is not empty）
L3: it = {((2,), [nats, fib]), …}, q = []
L4: vals = (2,), next_cloners = [nats, fib], it = {((3,), [nats, fib]), …}
L5: False
L7: q = [{((2, 1), [fib]), …}]
L8: q = [{((2, 1), [fib]), …}, {((3,), [nats, fib]), …}]
L2: True（q is not empty）
L3: it = {((2, 1), [fib]), …}, q = [{((3,), [nats, fib]), …}]
L4: vals = (2, 1), next_cloners = [fib], it = {((2, 2), [fib]), …}
L5: False
L7: q = [{((3,), [nats, fib]), …}, {((2, 1, 1), []), …}]
L8: q = [{((3,), [nats, fib]), …}, {((2, 1, 1), []), …}, {((2, 2), [fib]), …}]
L2: True（q is not empty）
L3: it = {((3,), [nats, fib]), …}, q = [{((2, 1, 1), []), …}, {((2, 2), [fib]), …}]
L4: vals = (3,), next_cloners = [nats, fib], it = {((5,), [nats, fib]), …}
L5: False
L7: q = [{((2, 1, 1), []), …}, {((2, 2), [fib]), …}, {((3, 1), [fib]), …}]
L8: q = [{((2, 1, 1), []), …}, {((2, 2), [fib]), …}, {((3, 1), [fib]), …}, {((5,), [nats, fib]), …}]
L2: True（q is not empty）
L3: it = {((2, 1, 1), []), …}, q = [{((2, 2), [fib]), …}, {((3, 1), [fib]), …}, {((5,), [nats, fib]), …}]
L4: vals = (2, 1, 1), next_cloners = [], it = {((2, 1, 1), []), …}
L5: True
L6: yield (2, 1, 1) # => (2, 1, 1)  # ここでやっと最初の組を yield！
L8: q = [{((2, 2), [fib]), …}, {((3, 1), [fib]), …}, {((5,), [nats, fib]), …}, {((2, 1, 1), []), …}]
  : 《中略》
L2:
L3: it = {((2, 1, 1), []), …}, q = [{((2, 2, 1), []), …}, {((2, 3), [fib]), …}, {((3, 1, 1), []), …}, {((3, 2), [fib]), …}, {((5, 1), [nats, fib]), …}, {((7,), [nats, fib]), …}]
L4: vals = (2, 1, 1), next_cloners = [], it = {((2, 1, 2), []), …}
L5: True
L6: yield (2, 1, 1) # => (2, 1, 1)
L8: q = [{((2, 2, 1), []), …}, {((2, 3), [fib]), …}, {((3, 1, 1), []), …}, {((3, 2), [fib]), …}, {((5, 1), [nats, fib]), …}, {((7,), [nats, fib]), …}, {((2, 1, 2), []), …}]
  : 《中略》
L6: yield (2, 2, 1) # => (2, 2, 1)
L8: q = [{((2, 3), [fib]), …}, {((3, 1, 1), []), …}, {((3, 2), [fib]), …}, {((5, 1), [nats, fib]), …}, {((7,), [nats, fib]), …}, {((2, 1, 2), []), …}, {((2, 2, 1), []), …}]
  : 《中略》
L6: yield (3, 1, 1) # => (3, 1, 1)
L8: q = [{((3, 2), [fib]), …}, {((5, 1), [nats, fib]), …}, {((7,), [nats, fib]), …}, {((2, 1, 2), []), …}, {((2, 2, 1), []), …}, {((2, 3, 1), []), …}, {((2, 4), [fib]), …}, {((3, 1, 1), []), …}]
  : 《以下略》

先ほどまでと比べてはるかに複雑になってきましたが、こちらもよく見ると、vals が3個未満のイテレータをセパレータとして、実際に yield する要素を持つ組が1次元に並んでいますよね？(^-^)
しかも各セパレータによって分割されている、yield 対象の組の連続が、テストケースで示した、

            expected = [
                (2, 1, 1),
                (2, 1, 1), (2, 2, 1),
                (3, 1, 1),
                (2, 1, 2), (2, 2, 1), (2, 3, 1),
                (3, 1, 1), (3, 2, 1),
                (5, 1, 1),
                # 以下略

と同じ構造になっていることに、気付きませんか？
こんなところにもヒントを潜ませておきました。気付いた方はいらっしゃったでしょうか*7。

あと、イテレータが有限の場合にどういう挙動になるのか、も見ておきましょう。
多くの方が（提出後のフィードバックで）改めて考えることになった、infinite_product([1, 2], [1, 2], [1, 2]) は、全て見ていくと以下のようになります（少々長いですがお付き合いくださいm(_ _)m）：

L1: q = [{((1,), [[1, 2], [1, 2]]), …}]
L2: True（q is not empty）
L3: it = {((1,), [[1, 2], [1, 2]]), …}, q = []
L4: vals = (1,), next_cloners = [[1, 2], [1, 2]], it = {((2,), [[1, 2], [1, 2]]), …}
L5: False
L7: q = [{((1, 1), [[1, 2]]), …}]
L8: q = [{((1, 1), [[1, 2]]), …}, {((2,), [[1, 2], [1, 2]]), …}]
L2: True（q is not empty）
L3: it = {((1, 1), [[1, 2]]), …}, q = [{((2,), [[1, 2], [1, 2]]), …}]
L4: vals = (1, 1), next_cloners = [[1, 2]], it = {((1, 2), [[1, 2]]), …}
L5: False
L7: q = [{((2,), [[1, 2], [1, 2]]), …}, {((1, 1, 1), []), …}]
L8: q = [{((2,), [[1, 2], [1, 2]]), …}, {((1, 1, 1), []), …}, {((1, 2), [[1, 2]]), …}]
L2: True（q is not empty）
L3: it = {((2,), [[1, 2], [1, 2]]), …}, q = [{((1, 1, 1), []), …}, {((1, 2), [[1, 2]]), …}]
L4: vals = (2,), next_cloners = [[1, 2], [1, 2]], it = {}   # 元のイテレータが [1, 2] なので次に列挙するものは残っていない！
L5: False
L7: q = [{((1, 1, 1), []), …}, {((1, 2), [[1, 2]]), …}, {((2, 1), [[1, 2]]), …}]
L8: q = [{((1, 1, 1), []), …}, {((1, 2), [[1, 2]]), …}, {((2, 1), [[1, 2]]), …}, {}]
L2: True（q is not empty）
L3: it = {((1, 1, 1), []), …}, q = [{((1, 2), [[1, 2]]), …}, {((2, 1), [[1, 2]]), …}, {}]
L4: vals = (1, 1, 1), next_cloners = [], it = {((1, 1, 2), []), …}
L5: True
L6: yield (1, 1, 1) # => (1, 1, 1)  # 最初の組を yield！
L8: q = [{((1, 2), [[1, 2]]), …}, {((2, 1), [[1, 2]]), …}, {}, {((1, 1, 2), []), …}]
L2: True（q is not empty）
L3: it = {((1, 2), [[1, 2]]), …}, q = [{((2, 1), [[1, 2]]), …}, {}, {((1, 1, 2), []), …}]
L4: vals = (1, 2), next_cloners = [[1, 2]], it = {} # 次に列挙するものが残っていない！
L5: False
L7: q = [{((2, 1), [[1, 2]]), …}, {}, {((1, 1, 2), []), …}, {((1, 2, 1), []), …}]
L8: q = [{((2, 1), [[1, 2]]), …}, {}, {((1, 1, 2), []), …}, {((1, 2, 1), []), …}, {}]
L2: True（q is not empty）
L3: it = {((2, 1), [[1, 2]]), …}, q = [{}, {((1, 1, 2), []), …}, {((1, 2, 1), []), …}, {}]
L4: vals = (2, 1), next_cloners = [[1, 2]], it = {((2, 2), [[1, 2]]), …}
L5: False
L7: q = [{}, {((1, 1, 2), []), …}, {((1, 2, 1), []), …}, {}, {((2, 1, 1), []), …}]
L8: q = [{}, {((1, 1, 2), []), …}, {((1, 2, 1), []), …}, {}, {((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}]
L2: True（q is not empty）
L3: it = {}, q = [{((1, 1, 2), []), …}, {((1, 2, 1), []), …}, {}, {((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}]
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: True（q is not empty）
L3: it = {((1, 1, 2), []), …}, q = [{((1, 2, 1), []), …}, {}, {((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}]
L4: vals = (1, 1, 2), next_cloners = [], it = {}    # 次に列挙するものが残っていない！
L5: True
L6: yield (1, 1, 2) # => (1, 1, 2)
L8: q = [{((1, 2, 1), []), …}, {}, {((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}, {}]
L2: True（q is not empty）
L3: it = {((1, 2, 1), []), …}, q = [{}, {((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}, {}]
L4: vals = (1, 2, 1), next_cloners = [], it = {((1, 2, 2), []), …}  # 次に列挙するものが残っていない！
L5: True
L6: yield (1, 2, 1) # => (1, 2, 1)
L8: q = [{}, {((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}, {}, {((1, 2, 2), []), …}]
L2: True（q is not empty）
L3: it = {}, q = [{((2, 1, 1), []), …}, {((2, 2), [[1, 2]]), …}, {}, {((1, 2, 2), []), …}]
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: True（q is not empty）
L3: it = {((2, 1, 1), []), …}, q = [{((2, 2), [[1, 2]]), …}, {}, {((1, 2, 2), []), …}]
L4: vals = (2, 1, 1), next_cloners = [], it = {((2, 1, 2), []), …}  # 次に列挙するものが残っていない！
L5: True
L6: yield (2, 1, 1) # => (2, 1, 1)
L8: q = [{((2, 2), [[1, 2]]), …}, {}, {((1, 2, 2), []), …}, {((2, 1, 2), []), …}]
L2: True（q is not empty）
L3: it = {((2, 2), [[1, 2]]), …}, q = [{}, {((1, 2, 2), []), …}, {((2, 1, 2), []), …}]
L4:2vals = (2, 2), next_cloners = [[1, 2]], it = {} # 次に列挙するものが残っていない！
L5: False
L7: q = [{}, {((1, 2, 2), []), …}, {((2, 1, 2), []), …}, {((2, 2, 1), []), …}]
L8: q = [{}, {((1, 2, 2), []), …}, {((2, 1, 2), []), …}, {((2, 2, 1), []), …}, {}]
L2: True（q is not empty）
L3: it = {}, q = [{((1, 2, 2), []), …}, {((2, 1, 2), []), …}, {((2, 2, 1), []), …}, {}]
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: True（q is not empty）
L3: it = {((1, 2, 2), []), …}, q = [{((2, 1, 2), []), …}, {((2, 2, 1), []), …}, {}]
L4: vals = (1, 2, 2), next_cloners = [], it = {}    # 次に列挙するものが残っていない！
L5: True
L6: yield (1, 2, 2) # => (1, 2, 2)
L8: q = [{((2, 1, 2), []), …}, {((2, 2, 1), []), …}, {}, {}]
L2: True（q is not empty）
L3: it = {((2, 1, 2), []), …}, q = [{((2, 2, 1), []), …}, {}, {}]
L4: vals = (2, 1, 2), next_cloners = [], it = {}    # 次に列挙するものが残っていない！
L5: True
L6: yield (2, 1, 2) # => (2, 1, 2)
L8: q = [{((2, 2, 1), []), …}, {}, {}, {}]
L2: True（q is not empty）
L3: it = {((2, 2, 1), []), …}, q = [{}, {}, {}]
L4: vals = (2, 2, 1), next_cloners = [], it = {((2, 2, 2), []), …}
L5: True
L6: yield (2, 2, 1) # => (2, 2, 1)
L8: q = [{}, {}, {}, {((2, 2, 2), []), …}]
L2: True（q is not empty）
L3: it = {}, q = [{}, {}, {((2, 2, 2), []), …}]
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: True（q is not empty）
L3: it = {}, q = [{}, {((2, 2, 2), []), …}]
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: True（q is not empty）
L3: it = {}, q = [{((2, 2, 2), []), …}]
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: True（q is not empty）
L3: it = {((2, 2, 2), []), …}, q = []
L4: vals = (2, 2, 2), next_cloners = [], it = {}    # 次に列挙するものが残っていない！
L5: True
L6: yield (2, 2, 2) # => (2, 2, 2)  #  最後の組を列挙
L8: q = [{}]
L2: True（q is not empty）
L3: it = {}, q = []
L9: pass    # it が空（＝next(it) が StopIteration を発生）なので飛ばして次へ
L2: False（q is empty）
END

詳解はしませんが、2点だけ。
ポイントは、「L9: pass」の行と、最後の「L2: False（q is empty）」の行。
有限の場合には、イテレータがいつか終わるのでその時に「L9」の行に移るのですが、ここでは何もせずに次のループに処理を移しているだけです。「何もしない」ということは、今まで使っていたイテレータをキューに戻していない、ということ。さらに言い換えると、『要らなくなったイテレータを適切に除去している』ということ。
追加のテストケースだけでなく、元のテストケースの4番目と5番目の、一方のイテレータが無限で一方が有限の場合でも、如何に上手く「イテレーションが終わったイテレータの値を排除するか」に苦労された方が多いと思います。
それが、「『何もしない』という行為によってキューから除去する」という、すこぶるシンプルな実装にできているのです(^-^)
そして、追加のテストケースで皆さま少し躓きかけたであろう、「全て有限で全て列挙しきったときにどうやってループを終了するか」。多くの方はフラグを導入して「infinite_product_process() から1件も yield されてこなかったらもう列挙すべきものは残ってないので終了」という実装になっていたと思います。
それが、「キューが空なら終了」という、これまたすこぶるシンプルなモノに(^-^)

どうやったらこんなの思いつくのか！？

「こんなコード思いつかないよ！」て声が聞こえてきそうですけれど、確かに私もゼロからこのコードを思いついたわけではありません。
あるコードを見て、この実装の着想を得たのですが、その仕組みの根底は、以下のようなかなりシンプルな考え方です。

無限を扱うコツは、その仕組みを見いだし、その「定義」を並べるようにすること。

これはこの問題シリーズ（全6問）を通して言いたかったことでもあります。
Lv.1 問題では、「『どのように列挙するか』だけを実装して、『どこまで列挙するか』はそれを利用する側に任せる」ということを説明しました（Lv.1 Ruby編解説 / Lv.1 Python編解説）。
Lv.2 問題の解説では明示的には述べていませんが、Ruby編/Python編ともに「ループはシンプルな無限ループであり、その内部で break はしていない」コードになっています。理由は先に述べた Lv.1 問題と全く同様です（Lv.2 Ruby編 / Lv.2 Python編）。

こういった思考は、関数型思考に繋がります。
所謂「関数型プログラミング」の世界では、ほとんどが関数定義の組合せでプログラムが構成されます。ループさえも関数の再帰呼出で表現し、言語仕様にすら存在しない言語も存在します。
さらに言語レベルで仕様として『遅延評価』を擁している言語の場合、無限が非常に扱いやすくなります。言語仕様に沿った定義を行うだけで、無限リストも簡単に定義でき、しかも必要なときにだけ必要な値を算出する仕組みになるので*8。

実際、私の解答例は、所謂「関数型言語」と呼ばれるものにも比較的移植しやすくなっています。
試しに Haskell に移植してみました*9

ちなみに。
その着想を得たという「あるコード」については…。

もう記事があまりにも長くなってしまいました(^_^;ので、後日別記事に上げるとします。

*1:北海道の大自然を満喫してきました♪

*2:より正確には『直積集合の各要素を列挙』ですね

*3:このややこしいめんどくさい問題にきちんと向き合ってプログラムをくみ上げる力があれば充分な技術力をお持ちですので胸を張って良いですよ^-^＞正解のみなさま

*4:以降毎回「（メソッド）」と書くのが面倒なので、一般的概念としての「関数」という名称のみ用います。

*5:「一発〜」の中には、1回目の挑戦で『真の正解』に辿り着いていた方の他に、私が最初のFBを送る前に再提出して『真の正解』に辿り着いた方も含まれます（つまり指摘を受けて修正再提出していただいた結果が『真の正解』だった方以外）。

*6:え？ 「2関数内で完結するように」とは言いましたが、関数内に別の関数/クラスを定義指定はいけないとは一言も言っていませんよ？（てか関数外に別関数を定義した解答もテストが通っていれば今回は正解扱いしちゃってたりもします実は…）

*7:んなもん分かるか、て声が聞こえてきそう^_^;

*8:もっとも『遅延評価』を言語レベルで用意していなくても、リストを「現在の値」と「次の値を算出する関数」の組として表現することで無限リストも表現できます。

*9:本当は、Pythonと同様、「引数はリストで与えるのではなく、可変長で指定できるように」「戻り値はリストではなく、与えられた引数の個数と型に応じたタプル」という動きにしたかったのですが、それを実現するには型クラスとかMonadとかをきちんと理解しなくてはならなさそうで、ちょっとそこまで手が出せないでいます^_^; 誰か教えて^_^;