配列同士の組み合わせを出力する(多重ループの展開)

Posted by Hiraku on 2009-12-14

どうでもいいようなコードをPHPで書くような記事ばっかりな訳ですが、今回もそのネタです。サンプルコードがPHPなのはご容赦くださいませ。

$a = array(1,2); $b = array('a', 'b');のとき、$aからひとつ、$bからひとつ要素を取り出して組み合わせを作る。考えうるすべての組み合わせを出力せよ。

こういう感じの問題があったら、普通はこう書くでしょう。


foreach ($a as $val1) {
    foreach ($b as $val2) {
        print "$val1, $val2\n";
    }
}

では更に$c, $dも組み合わせろと言われたら? まあループを更に多重にしてやればよいですね。


foreach ($a as $val1) {
    foreach ($b as $val2) {
        foreach ($c as $val3) {
            foreach ($d as $val4) {
                print "$val1, $val2, $val3, $val4\n");
            }
        }
    }
}

ではもっと問題を抽象化して、配列が任意個になったとき、組み合わせをつくる関数は書けるでしょうか?

これすなわち「任意次元の多重ループを展開できるか」という問題です。筆者はけっこうこの問題に悩みました。ググっても出てきてくれるのは関数型言語の、再帰の山のような答えばかりだったので。。。

foreach()のネストを文字列で作成して、みんな大好きなeval()を使うという手もありますが、ちょっとエレガントさに欠けます。直球で書けないでしょうか。

解法に入る前に、問題を整理しておきましょう。求められている関数は以下の機能を持ちます。

  1. 任意個の1次元配列を受け取る
  2. 受け取った配列同士の、考えうるすべての組み合わせを作る
  3. できた組み合わせにprint()を作用させる

できれば最後のprint()のところは、任意のコールバック関数が使えた方が汎用性が高くなってよいですね。あるいは関数から切り離してもよさそうです。

ひとまずメモリ消費には目をつむって、組み合わせを作ることを考えてみます。

こういう問題は、とりあえず引数が少ない場合を考えて、それを再帰できないか考えるのが定石。というわけで引数が2個の場合に限定して書きます。これなら簡単ですね。


function combine($a, $b) {
    $result = array();
    foreach ($a as $val1) {
        foreach ($b as $val2) {
            $result[] = array($val1, $val2);
        }
    }
	
    return $result;
}
//////
print_r(combine(array(0,1), array(0,1))); 
/*
[
  [0,0],
  [0,1],
  [1,0],
  [1,1]
]
*/

さて、この$resultと次の$cとの組み合わせを作れないでしょうか。作れたら何とかなりそうですね。

array($val1, $val2)だとうまくいきませんので、array_merge()に修正してみます。


function combine($a, $b) {
    $result = array();
    foreach ($a as $val1) {
        foreach ($b as $val2) {
            $result[] = array_merge((array)$val1, (array)$val2);
        }
    }
	
    return $result;
}
//////
print_r(combine(<さっきの結果>, array(0,1))); 
/*
[
  [0,0,0],
  [0,0,1],
  [0,1,0],
  ...(以下略)
]
*/

これで解けました。あとは再帰するところを作れば終わり。引数ですが、可変長引数で扱うようにしてみます。


function combine() {
    $args = func_get_args();

    $a = array_shift($args);
    $b = array_shift($args);

    $result = array();
    foreach ($a as $val1) {
        foreach ($b as $val2) {
            $result[] = array_merge((array)$val1, (array)$val2);
        }
    }

    if (count($args) > 0) {
        foreach ($args as $arg) {
            $result = combine($result, $arg);
        }
    }

    return $result;
}
$p = range(0,1);
print_r(combine($p,$p,$p,$p));

メモリ効率悪いし、array_merge()を呼ぶ回数はもっと減らせると思うけど、とりあえずこれで動作はします。眠くなったので今日はここまで。



keyword: PHP

codingの最新記事

×

この広告は180日以上新しい記事の投稿がないブログに表示されております。