【PHP】２進数で全ての組み合わせを取得する

自動テストなどで全ての組み合わせを取得したいというケースがあるかと思います。

やり方はいくつかあると思いますが、今回は2進数を使って全ての組み合わせを作ります。

この記事のゴール
前提条件
サンプルコード
アルゴリズムの確認
扱える配列要素数の上限
補足

この記事のゴール

全ての組み合わせを取得する関数の仕組みが理解できる

前提条件

これは自作の関数です。
PHPの性質を使っています。
飽く迄、一手法です。やりかたは他にもいくつかあります。
コードの中で並び順は考慮していません。（OSのコマンドでソートしています。）
PHP8.1.xで動作確認しています。

サンプルコード

getAllCombinations.php とでも命名しておきます。

getAllCombinations() の引数に1次元配列で組み合わせ対象の要素を渡すと、

組み合わせのリストを2次元配列で返します。

<?php

function getAllCombinations(array $items)
{
    if (empty($items)) {
        throw new \Exception("Empty items set.");
    }
    $count = count($items);
    $numberOfAllPatterns = 2 ** $count;
    $bitPatterns = [];
    $format = '%0' . $count . 'b';
    for ($i = 1; $i < $numberOfAllPatterns; $i++) {
        $bitPatterns[] = sprintf($format, $i);
    }
    $combinations = [];
    foreach ($bitPatterns as $bits) {
        $combination = [];
        foreach (str_split($bits) as $index => $bit) {
            if ((bool) $bit) {
                $combination[] = $items[$index];
            }
        }
        $combinations[] = $combination;
    }
    return $combinations;
}

$items = ['A', 'B', 'C', 'D', 'E'];
$combinations = getAllCombinations($items);
foreach ($combinations as $index => $combination) {
    echo implode(',', $combination) . "\n";
}

最後の箇所で、関数 getAllCombinations() から受け取った配列を

implode() でカンマつなぎで表示しています。

見やすいように辞書順ソートで行番号を付けて表示してみます。（Ubuntu CLI上）

php -f getAllCombinations.php | sort | awk '{print NR, $0}'

1 A
2 A,B
3 A,B,C
4 A,B,C,D
5 A,B,C,D,E
6 A,B,C,E
7 A,B,D
8 A,B,D,E
9 A,B,E
10 A,C
11 A,C,D
12 A,C,D,E
13 A,C,E
14 A,D
15 A,D,E
16 A,E
17 B
18 B,C
19 B,C,D
20 B,C,D,E
21 B,C,E
22 B,D
23 B,D,E
24 B,E
25 C
26 C,D
27 C,D,E
28 C,E
29 D
30 D,E
31 E

渡した要素はA, B, C, D, E の5個、各々、有り/無し２通りの５要素分の組み合わせで、

２＾５（２の５乗）＝３２、そのうち、全てが「無し」の１通りを除外して全３１通り。

件数は合っています。組み合わせの重複もありませんね。

アルゴリズムの確認

アルゴリズムを見ていきます。

function getAllCombinations(array $items)
{
    if (empty($items)) {
        throw new \Exception("Empty items set.");
    }

引数 $items は配列であり、要素があることが前提です。

    $count = count($items);
    $numberOfAllPatterns = 2 ** $count;

引数配列の要素数を取得し、全パターン数を算出して $numberOfAllPatterns に格納しています。

全パターン数は２の $count 乗です。

    $bitPatterns = [];
    $format = '%0' . $count . 'b';
    for ($i = 1; $i < $numberOfAllPatterns; $i++) {
        $bitPatterns[] = sprintf($format, $i);
    }

組み合わせを表現するための2進数文字列を入れる配列 $bitPatterns を初期化しています。

sprintf() で使用するフォーマットを $fotmat に格納しています。

$count 桁の２進数で頭ゼロ埋めです。今回は要素が5個なので、 ‘%05b’ の書式となります。

全て「無し(=0)」を含めないように、for文の開始を $i = 1 としています。

$i は10進数で上限までカウントし、それを ‘%05b’ の書式で2進数の文字列に変換してから

$bitPatterns[] に格納しています。今回の5要素の組み合わせでは次のようになります。

文字列の左から順に、各要素の有り/無しを表現しています。

1 なら有り、0なら無しです。今回の要素は、A,B,C,D,E の順なので、

10101 の組み合わせなら、A,C,E となります。

    $combinations = [];
    foreach ($bitPatterns as $bits) {
        $combination = [];
        foreach (str_split($bits) as $index => $bit) {
            if ((bool) $bit) {
                $combination[] = $items[$index];
            }
        }
        $combinations[] = $combination;
    }

組み合わせ用配列 $combinations を初期化します。

$bitPatterns の各組み合わせについてループを回します。

各ループ毎の組み合わせ配列 $combination を初期化します。

２進数文字列を1文字ごとに分割して配列化し、各要素についてループを回します。

その文字（”0″ または “1”）を (bool) で boolean に型変換して

if文の条件判定に使っています。文字が”1″なら true になるので、

該当する要素(A,B,C,D,Eの該当するもの)を $combination に格納します。

文字ごとのループが終わったところで $combination を $combinations に格納します。

    return $combinations;
}

$combinations を返して関数の処理は終了です。

これで返る内容は次の通りです。

[
	["E"],
	["D"],
	["D", "E"],
	["C"],
	["C", "E"],
	["C", "D"],
	["C", "D", "E"],
	["B"],
	["B", "E"],
	["B", "D"],
	["B", "D", "E"],
	["B", "C"],
	["B", "C", "E"],
	["B", "C", "D"],
	["B", "C", "D", "E"],
	["A"],
	["A", "E"],
	["A", "D"],
	["A", "D", "E"],
	["A", "C"],
	["A", "C", "E"],
	["A", "C", "D"],
	["A", "C", "D", "E"],
	["A", "B"],
	["A", "B", "E"],
	["A", "B", "D"],
	["A", "B", "D", "E"],
	["A", "B", "C"],
	["A", "B", "C", "E"],
	["A", "B", "C", "D"],
	["A", "B", "C", "D", "E"],
]

並び順が逆ですね。でも、テストケースを網羅するだけが目的であれば気になりません。

$items = ['A', 'B', 'C', 'D', 'E'];
$combinations = getAllCombinations($items);
foreach ($combinations as $index => $combination) {
    echo implode(',', $combination) . "\n";
}

呼び出し側の処理です。組み合わせたい要素を $items に格納します。

getAllCombinations($items) で組み合わせの結果の配列を $combinations に格納します。

組み合わせリストについてループを回し、各リストについて、

組み合わせの配列をカンマつなぎで標準出力へ出力しています。