PHPで無限ストリームの直積(2)

PHP

前回Iterator2個を先頭から読んで要素同士を組み合わせたすべての値を生成するIteratorを作成した。
terazzo.hatenadiary.org
今回はこれを3個に増やしてみる。

対角線で増やしていくやつの3次元版は難しいので、バリエーションの矩形で考えて増分のL字部分を出力するやつを立体化する。

/**
 * 無限Iterator2つの直積を無限Iteratorとして生成する。
*/
function iterator_product2(\Iterator $iter1, \Iterator $iter2): \Iterator
{
    foreach (iterator_zip(gradual_iterator($iter1), gradual_iterator($iter2)) as [$xs, $ys]) {
        $x = array_pop($xs);
        $y = array_pop($ys);
        // 増えたXに対してY辺を出力
        yield from array_map(fn($v) => [$x, $v], $ys);
        // 増えたYに対してX辺を出力
        yield from array_map(fn($v) => [$v, $y], $xs);
        // X,Yを出力
        yield [$x, $y];
    }
}

これを単純に3個にする。

/**
 * 無限Iterator3つの直積を無限Iteratorとして生成する。
 */
function iterator_product3(\Iterator $iter1, \Iterator $iter2, \Iterator $iter3): \Iterator
{
    foreach (
        iterator_zip(
            gradual_iterator($iter1),
            gradual_iterator($iter2),
            gradual_iterator($iter3)
        ) as [$xs, $ys, $zs]
    ) {
        $x = array_pop($xs);
        $y = array_pop($ys);
        $z = array_pop($zs);

        // 増えたXに対してYZ面を出力
        foreach ($ys as $v) {
            foreach ($zs as $w) {
                yield [$x, $v, $w];
            }
        }
        // 増えたYに対してXZ面を出力
        foreach ($xs as $v) {
            foreach ($zs as $w) {
                yield [$v, $y, $w];
            }
        }
        // 増えたZに対してXY面を出力
        foreach ($xs as $v) {
            foreach ($ys as $w) {
                yield [$v, $w, $z];
            }
        }
        // 増えたXYに対してZ辺を出力
        yield from array_map(fn($v) => [$x, $y, $v], $zs);
        // 増えたXZに対してY辺を出力
        yield from array_map(fn($v) => [$x, $v, $z], $ys);
        // 増えたYZに対してX辺を出力
        yield from array_map(fn($v) => [$v, $y, $z], $xs);
        // X,Y,Zを出力
        yield [$x, $y, $z];
    }
}

テスツ

    public function test_iterator_product3()
    {
        $iterator1 = sequence(1);
        $iterator2 = sequence(1);
        $iterator3 = sequence(1);
        $iterator = iterator_product3($iterator1, $iterator2, $iterator3);
        $result = iterator_take($iterator, 27);
        $expected = [
            [1, 1, 1],
            [2, 1, 1],
            [1, 2, 1],
            [1, 1, 2],
            [2, 2, 1],
            [2, 1, 2],
            [1, 2, 2],
            [2, 2, 2],
            [3, 1, 1],
            [3, 1, 2],
            [3, 2, 1],
            [3, 2, 2],
            [1, 3, 1],
            [1, 3, 2],
            [2, 3, 1],
            [2, 3, 2],
            [1, 1, 3],
            [1, 2, 3],
            [2, 1, 3],
            [2, 2, 3],
            [3, 3, 1],
            [3, 3, 2],
            [3, 1, 3],
            [3, 2, 3],
            [1, 3, 3],
            [2, 3, 3],
            [3, 3, 3]
        ];
        $this->assertEquals($expected, $result);
    }

まあ動いとるね。
gradual_iterator、iterator_take、iterator_zip、sequenceとかは前回作ったやつです。

一応説明すると、3つの無限イテレータをXYZ軸の立方体で考えて、増分に対する面と辺と頂点の部分を出力していくイメージです。

XYZの3次元で考えて増分の面と辺と頂点を新たに出力していく

4つ以上の無限イテレータの直積についても同じような考えで行けそう。
整理としては、「各イテレータを「次元軸」、それぞれの新規の値とそれまでの値を「点と辺」に見立てて、各次元の「点と辺」からどちらかを選んだすべての組み合わせに対して値を生成する(ただし、すべてが辺のものは出力済みなのでスキップする)」となる。

さて、この「面」を出す部分をよく見てみると

        // 増えたXに対してYZ面を出力
        foreach ($ys as $v) {
            foreach ($zs as $w) {
                yield [$x, $v, $w];
            }
        }

これ有限の2配列の直積ですよね。
てことのはn個の無限ストリームの直積を出すにはn-1個の配列の直積が取れれば良そうだ。(つづく)