組み合わせ
配列で与えられた異なる n個 の要素の中から，異なる r個 を取る組み合わせを全て取得します。
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でも実装してみる
/**
* 組み合わせ
*
* @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));