COMPANY SERVICE STAFF BLOG NEWS CONTACT

STAFF BLOG

スタッフブログ

NOTE

雑記

2024.02.01

組み合わせを再帰関数で列挙する

雑記

組み合わせを列挙するとは?

例えば、次のようなデータがあるとします。

  • ・果物:りんご、ぶどう、ばなな
  • ・値段:100、150、200、250
  • ・個数:1、2、3、4、5

このデータに対して、「果物、値段、個数の組み合わせを列挙してください」と言われたら、
以下のようになると思います。

  • ・りんご、100、1
  • ・りんご、100、2
  • ・りんご、100、3
  •  …
  • ・ばなな、250、5

これをここでは「組み合わせを列挙する」と呼ぶことにします。

それfor文でよくない?

おっしゃる通りです。
先ほどの例をfor文(foreach文)で実装すると以下のようになります。

<?php

$fruits = ['りんご', 'ぶどう', 'ばなな'];
$prices = [100, 150, 200, 250];
$nums = [1, 2, 3, 4, 5];

// "果物" "値段" "個数" の組み合わせ
$enums = [];

// "果物" "値段" "個数" の組み合わせを列挙
foreach ($fruits as $fruit) {
	foreach ($prices as $price) {
		foreach ($nums as $num) {
			$enums[] = [$fruit, $price, $num];
		}
	}
}

var_dump($enums);

ただ、これには2つの問題があります。

  • ・組み合わせの種類数が変わったときに、foreachの個数も変えないといけない
  • ・組み合わせの種類数が多くなったときに、foreachをたくさん書くのが大変

これらの問題を再帰関数を使用することで解決します。

再帰関数による実装

<?php

$elems = [
	['りんご', 'ぶどう', 'ばなな'],
	[100, 150, 200, 250],
	[1, 2, 3, 4, 5],
];

// "果物" "値段" "個数" の組み合わせ
$enums = [];
$enum = [];

// "果物" "値段" "個数" の組み合わせを列挙
$dfs = function (int $idx = 0) use (&$dfs, &$enums, &$enum, $elems): void {
	if ($idx >= count($elems)) {
		$enums[] = $enum;
		return;
	}
	foreach ($elems[$idx] as $elem) {
		$enum[] = $elem;
		$dfs($idx + 1);
		array_pop($enum);
	}
};

$dfs();

var_dump($enums);

組み合わせの種類数が変わった場合は「$elems」を変更するだけで済むようになりました。
また、組み合わせの種類数が多くなったとしても記述量は大して増えません。

ちなみに無名関数を使用しているのは、useによって不要な引数を渡さないで済むからです。

おわりに

組み合わせの列挙はテストのパターンの洗い出しで使う機会があります。

ツールでも代用できますが、細かな制御を入れたり、他のツールと組み合わせて使ったりするときは、
自前で実装することもしばしば。

パターンが多くなりそうなときは再帰関数を使用してみてはいかがでしょうか。

この記事を書いた人

ノコ

入社年2021年

出身地岩手

業務内容Web開発

特技・趣味ゲーム、競プロ、数学

雑記に関する記事一覧

TOP