任意の文字集合から成るM桁のN進数をジェネレータで生成する

はじめに

• 1時間以内に解けなければプログラマ失格となってしまう5つの問題をPHPで解く

ここの解答5にて、3進数8桁を生成する解法を使いました。しかし例えばこれがもし62進数10桁のような膨大なスケールになったと仮定すると、以下のような問題が発生します。

• この解法を使うと整数がオーバーフローする。かといってこれのためにわざわざGMP数やBCMath関数を使うかというと悩みどころ。
• 再帰させて配列にする方法だと配列生成処理が終わらないあるいはメモリ制限をオーバーする。時間がかかるにしても逐次処理させていきたい。

そこで…PHP5.5で導入されたジェネレータの出番なんです。

実装

※ ジェネレータ内でreturn出来るようになったのはPHP7以降のようであり、それより古い環境に対応させるためにreturnを使わずに済む条件分岐に書き換えました。

ジェネレータ定義

• 長さが2以上のとき、現コールスタックから見た最大桁を生成し、そのそれぞれについて、残りの全ての桁が結合されたものを再帰呼び出しによって生成します。これらを結合して返します。
• 長さが2未満1以上のとき、1桁だけを生成して返します。
• 長さが1未満のとき、生成を即座に終了します。実際に再帰でこの呼び出しが行われることはありません。

function generate(array $chars, $length) {
    if ($length >= 2) {
        foreach ($chars as $char) {
            foreach (generate($chars, $length - 1) as $string) {
                yield $char . $string;
            }
        }
    } elseif ($length >= 1) {
        foreach ($chars as $char) {
            yield $char;
        }
    }
}

(参考) ジェネレータの代わりに配列を生成する場合のコード

function collect(array $chars, $length) {
    if ($length >= 2) {
        $strings = [];
        foreach ($chars as $char) {
            foreach (collect($chars, $length - 1) as $string) {
                $strings[] = $char . $string;
            }
        }
        return $strings;
    } elseif ($length >= 1) {
        return $chars;
    } else {
        return [];
    }
}

使用例

// 半角英数字とアンダースコア
$chars = array_merge(
    range(0, 9),
    range('a', 'z'),
    range('A', 'Z'),
    ['_']
);

// 3桁で出力
foreach (generate($chars, 3) as $string) {
    echo $string . PHP_EOL;
}

/*
000
001
002
003
004
...
__W
__X
__Y
__Z
___
*/