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

前回→
terazzo.hatenadiary.org
無限ストリーム(Iterator)の直積を4個以上にも対応していきたい。
方針を立てるために前回のストリーム3個の場合のコードを見ながら、引き続き各Iteratorを「次元」、値のリストを「辺」、値を「点」とみなすメタファーを使って疑似コードを書いてみる。

function iterator_cartesian_product(\Iterator ...$iters): \Iterator
{
    // ①引数を生成済みの値を段階的に出力するIteratorに変換
    $gradual_iters = array_map(gradual_iterator(...), $iterators):
    // ②それを同時に進行するIteratorを作ってforeachで回す
    foreach(iterator_zip(...$gradual_iters) as $dimensions) {
        ③各次元の値を「辺(出力済みの値のリスト)」と「点(新たに出力された値)」に分解
        ④各次元から辺または点のどちらかを選んだすべての組み合わせのリストを作成
        foreach(④ as 各次元から辺または点のどちらかを選んだリスト) {
            if (すべてが辺) continue; // 出力済み
            ⑤ yield from [点,点,点...]のリスト
        }
    }
}

⑤の部分が有限リストの直積で出せそうだが、④の各次元から辺or点を選ぶ部分ももよく見たら直積(2×2×...)になってる。これを「閑話休題 - terazzoの日記」の配列の直積で書いてみる。

その前に準備としてgradual_iterator()を直して[出力済みの値のリスト,[新たな値]]を出すようにする。あとから分解するの面倒だからね。

function gradual_iterator(\Iterator $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last]];
        $cached[] = $last;
    }
}
// こっちは変更なし
function iterator_zip(\Iterator ...$iterators): \Iterator
{
    while (array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)) {
        yield array_map(fn($iter) => $iter->current(), $iterators);
        array_walk($iterators, fn($iter) => $iter->next());
    }
}

これとこの前作った配列の直積を出す関数を使って

function array_cartesian_product(array ...$arrs): array
{
    return array_reduce($arrs, fn($acc, $arr) => array_reduce(array_map(fn($v) => array_map(fn($r) => [...$r, $v], $acc), $arr), array_merge(...), []),[[]]);
}

すると無限ストリーム(Iterator)の直積は以下のように書ける

function iterator_cartesian_product(\Iterator ...$iterators): \Iterator
{
    foreach (iterator_zip(...array_map(gradual_iterator(...), $iterators)) as $dimensions) {
        $configurations = array_cartesian_product(...$dimensions);
        array_shift($configurations);
        foreach ($configurations as $configuration) {
            yield from array_cartesian_product(...$configuration);
        }
    }
}

$configurations(各次元から辺または点を選んだもの)の一つ目はすべて辺(出力済みの値)なのでarray_shiftで除去しています。手抜きだね。
内側のforeachはarray_mapとarray_mergeでも書けるけどメモリすごく食うのでforeachで十分。

テストとしてシーケンス4個をproductして最初の10個と9991～10000個目をみてみる。

    public function test_iterator_product()
    {
        $iterator = iterator_cartesian_product(sequence(0), sequence(0), sequence(0), sequence(0));
        $result = iterator_take($iterator, 10000);
        $result = array_map(fn($v) => implode('', $v), $result);
        $head10 = array_slice($result, 0, 10);
        $tail10 = array_slice($result, -10);
        $this->assertEquals(['0000', '1000', '0100', '1100', '0010', '1010', '0110', '1110', '0001', '1001'], $head10);
        $this->assertEquals(['0999', '1999', '2999', '3999', '4999', '5999', '6999', '7999', '8999', '9999'], $tail10);
    }

ちゃんと網羅できてるっぽい。
有限のIteratorが混ざってる場合にも対応したいですね。