組み合わせ

配列で与えられた異なる n個の要素の中から，異なる r個を取る組み合わせを全て取得します。

PHPで実装

combination.php

/**
 * コンビネーション 組み合わせ nCr (0 ≦ r ≦ n)
 *
 * @param array $arr 選ぶ元となる配列
 * @param int $r １組あたりの要素数
 * @return null|array
 */
function combination(array $arr, int $r): ?array
{
    // 重複した値を削除して，数値添字配列にする
    $arr = array_values(array_unique($arr));

    $n = count($arr);
    $result = []; // 最終的に二次元配列にして返す

    // nCr の条件に一致していなければ null を返す
    if($r < 0 || $n < $r){ return null; }
    
    if($r === 1){
        foreach($arr as $item){
            $result[] = [$item];
        }
    }
    
    if($r > 1){
        // n - r + 1 回ループ
        for($i = 0; $i < $n-$r+1; $i++){
            // $sliced は $i + 1 番目から末尾までの要素
            $sliced = array_slice($arr, $i + 1);
            // 再帰処理 二次元配列が返ってくる
            $recursion = combination($sliced, $r - 1);
            foreach($recursion as $one_set){
                array_unshift($one_set, $arr[$i]);
                $result[] = $one_set;
            }
        }
    }

    return $result;
}

使い方

// 4 C 2 = 6(組)
$arr = ['A', 'B', 'C', 'D'];
print_r(combination($arr, 2));

結果

Array
(
    [0] => Array
        (
            [0] => A
            [1] => B
        )

    [1] => Array
        (
            [0] => A
            [1] => C
        )

    [2] => Array
        (
            [0] => A
            [1] => D
        )

    [3] => Array
        (
            [0] => B
            [1] => C
        )

    [4] => Array
        (
            [0] => B
            [1] => D
        )

    [5] => Array
        (
            [0] => C
            [1] => D
        )

)

解説

組み合わせ（コンビネーション）の総数の求め方と，プログラムでのアルゴリズムを解説します。

組み合わせの計算

異なる n個の要素の中から，異なる r個を取る組み合わせの総数は

nCr = \frac{nPr}{r!}  \quad (0 ≦ r ≦ n)

例えば，7人の中から3人組を選ぶ組み合わせを考えてみます。

3つの席があるとすると，座席の座り方の総数は **7×6×5=210（通り）です。
これが順列（permutation）**です。

しかし，これだと重複が生じます。
(Aさん, Bさん, Cさん) と (Bさん, Aさん, Cさん)
この２つは並び順は異なりますが，組み合わせとしては同じです。

ですから重複する数で割る必要があります。

3人が3つの座席に座る時の並び方は 3!=6（通り）(※) あります。

つまり，210 を 6 で割れば良いのです。210/6 = 35 (組)

7人の中から3人組を選ぶ組み合わせの総数は 35 であることがわかります。

※ 異なるn個の要素のすべてを1列に並べる順列の総数を n! と表現します。

nPn = n!

ちなみに 0! = 1，nP0 = 1 です。

アルゴリズム

配列をループして，特定の要素を必ず含む組み合わせを考えます。

7C3 の具体例で考えます。
7つの要素を持つ配列 ['A', 'B', 'C', 'D', 'E', 'F', 'G'] があります。

n - r + 1 回ループ処理をします。nCr = 7C3 なので 7-3+1=5（回）

「A」を含むすべての組み合わせを計算（6C2）
「A」を含まず，「B」を含むすべての組み合わせを計算（5C2）
「A」「B」を含まず，「C」を含むすべての組み合わせを計算（4C2）
「A」「B」「C」を含まず，「D」を含むすべての組み合わせを計算（3C2）
「A」「B」「C」「D」を含まず，「E」を含むすべての組み合わせを計算（2C2）

1回目のループでは，「A」を除いた ['B', 'C', 'D', 'E', 'F', 'G'] の中から2つの要素の組を取り出します。取り出した後に，先頭に「A」を追加します。
すると「A」を含むすべての組み合わせが得られます。

2回目以降のループも同じです。特定の人を必ず含む3人の組を取り出すには，残る2席に座る人を決めれば良いのです。

では，なぜ n - r + 1 回のループになるのでしょうか？

ループ回数を i 回目と表現すると

6C2 → 5C2 → 4C2 → 3C2 → 2C2

これは n-i C r-1 となっています。
ここで n - i = r - 1 となる時が最後のループになります。

i について計算すると i = n - r + 1 になります。

最後のループは，「E」を必ず含み，残りの2人を「F」と「G」から選ぶ（2C2）のです。
ですから当然，最後は nCr-1（n = r-1）になるのです。

各々のループの中では再帰処理が発生します。

「A」を含むすべての組み合わせを計算（6C2）

ここでは ['B', 'C', 'D', 'E', 'F', 'G'] の6つの中から2つを選ぶ組み合わせを計算しています。さらにその中では，['C', 'D', 'E', 'F', 'G'] の5つの中から1つを選ぶ組み合わせを計算しています。

JavaScriptでも実装してみる

combination.js

/**
 * 組み合わせ
 * 
 * @param {Array} array 
 * @param {Number} r
 */
const combination = (array, r) => {
    
    const arr = uniq(array);
    const result = [];
    const n = arr.length;

    if(r < 0 || n < r){
        return;
    }
    
    if(r === 1){
        arr.forEach(el => result.push([el]));
    }
    
    if(r > 1){
        for(let i = 0; i < n-r+1; i++){    
            const sliced = arr.slice(i + 1);
            const recursion = combination(sliced, r - 1);
            recursion.forEach(one_set => result.push([arr[i]].concat(one_set)));        
        }
    }
    
    return result;
};


/**
 * 配列の重複を削除
 * 
 * @param {Array} array 
 * 
 */
const uniq = (array) => {
    if(! Array.isArray(array)){
        return;
    }
    return [...new Set(array)];
};

const array = ['A', 'B', 'C', 'D'];
console.log(combination(array, 2));

参考

PHPで組合せをすべて表示