PHP
アルゴリズム

PHPで直積計算

More than 1 year has passed since last update.


非再帰版

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 (
),
)
*/