PHPで直積計算

  • 7
    いいね
  • 6
    コメント

非再帰版

Pythonの実装を参考に非再帰版で書き直しました。なかなかこんな書き方思いつかないよ…

<?php

function direct_product(array ...$arrays)
{
    $result = [[]];
    foreach ($arrays as $array) {
        $tmp = [];
        foreach ($result as $x) {
            foreach ($array as $y) {
                $tmp[] = array_merge($x, [$y]);
            }
        }
        $result = $tmp;
    }
    return $result;
}

var_export(direct_product(['A', 'B', 'C'], ['a'], [1, 2]));
/*
array (
  0 => 
  array (
    0 => 'A',
    1 => 'a',
    2 => 1,
  ),
  1 => 
  array (
    0 => 'A',
    1 => 'a',
    2 => 2,
  ),
  2 => 
  array (
    0 => 'B',
    1 => 'a',
    2 => 1,
  ),
  3 => 
  array (
    0 => 'B',
    1 => 'a',
    2 => 2,
  ),
  4 => 
  array (
    0 => 'C',
    1 => 'a',
    2 => 1,
  ),
  5 => 
  array (
    0 => 'C',
    1 => 'a',
    2 => 2,
  ),
)
*/

var_export(direct_product(['A', 'B', 'C'], [], [1, 2]));
/*
array (
)
*/

var_export(direct_product());
/*
array (
  0 => 
  array (
  ),
)
*/

↑最後のやつって数学的に正しいのだろうか?

再帰ジェネレータ版

一応こちらのほうが省メモリです。

<?php

function direct_product(array ...$arrays)
{
    if (!$arrays) {
        yield [];
    } elseif ($tails = array_pop($arrays)) {
        foreach (direct_product(...$arrays) as $body) {
            foreach ($tails as $tail) {
                yield array_merge($body, [$tail]);
            }
        }
    }
}

var_export(iterator_to_array(direct_product(['A', 'B', 'C'], ['a'], [1, 2])));
/*
array (
  0 => 
  array (
    0 => 'A',
    1 => 'a',
    2 => 1,
  ),
  1 => 
  array (
    0 => 'A',
    1 => 'a',
    2 => 2,
  ),
  2 => 
  array (
    0 => 'B',
    1 => 'a',
    2 => 1,
  ),
  3 => 
  array (
    0 => 'B',
    1 => 'a',
    2 => 2,
  ),
  4 => 
  array (
    0 => 'C',
    1 => 'a',
    2 => 1,
  ),
  5 => 
  array (
    0 => 'C',
    1 => 'a',
    2 => 2,
  ),
)
*/

var_export(iterator_to_array(direct_product(['A', 'B', 'C'], [], [1, 2])));
/*
array (
)
*/

var_export(iterator_to_array(direct_product()));
/*
array (
  0 => 
  array (
  ),
)
*/