Math

PHP で順列と組合せをプログラムに落とし込む方法

はじめに

オタク友達との雑談にて、ホロライブ所属タレント同士のコラボって何パターンあるんだろうねって話になったが、その場で暗算ができずに会話を盛り上げることができなかった。同じ過ちを繰り返さない為に、PHP で順列と組合せをプログラム化して、簡単な解説と一緒に情報を残してみる。

検証環境

解説

順列 は、異なる n 個から r 個選んで順番に並べたものです。

公式は nPr = n! / (n – r)! になります。

組合せ は、異なる n 個から r 個選んで並べたものです。

公式は nCr = n! / r!(n – r)! になります。

! は 階乗 を表す記号です。

順列 と 組合せ の大きな違いは「順番を考慮するかどうか」です。

例えば、秋の大運動会の団体リレーで 5 人から 3 人を選抜した場合の走順と構成を求められたとします。

「走順」は 順列 で考えます。

下記のように、公式に当てはめて計算すると答えは 60 通りになります。

5P3 = 5! / (5 - 3)! = 5 × 4 × 3 × 2 × 1 / 2 × 1 = 5 × 4 × 3 = 60

PHP でプログラムに落とし込むと下記のようになります。

function nPr(int $n, int $r): ?int {
  return $n < $r ? null : ($r ? nPr($n - 1, $r - 1) * $n : 1);
}

0! = 1, nP0 = n! / n! = 1 で組み込んでいます。

構成は 組合せ で考えます。

下記のように、公式に当てはめて計算すると答えは 10 通りになります。

5C3 = 5P3 / 3! = 60 / 3 × 2 × 1 = 10

PHP でプログラムに落とし込むと下記のようになります。

function nCr(int $n, int $r): ?int {
  if ($r > $n) return null;
  elseif ($n - $r < $r) return nCr($n, $n - $r);

  $result = 1;
  for ($i = 0; $i < $r; $i++) $result *= ($n - $i) / ($i + 1);
  return $result;
}

nC0 = 1 で組み込んでいます。

また、nCr = nC(n-r) で組み込んでいます。なぜなら、n 個から r 個選ぶことは残りの選ばない n – r 個を選ぶのと同じだからです。

では、ホロライブ所属タレント同士のコラボが何パターンあるのか考えます。

ホロライブ（JP, ID, EN）のタレントは 2021 年 8 月時点で卒業生の桐生ココを除く 42 名、2 名コラボの 組合せ は下記のようになります。

42C2 = 42 × 41 / 2 × 1 = 21 × 41 = 861

3 名コラボの 組合せ は下記のようになります。

42C3 = 42 × 41 × 40 / 3 × 2 × 1 = 7 × 41 × 40 = 11480

一生コラボ動画が見れます。

以上です。

おわりに

順列 と組合せ の知識は、実務や日常会話で大いに役立ちます。

例えば、アフィリエイト広告の 組合せ を算出して表示割合を決める時、飲み会で腐女子からカップリングパターンを聞かれた時とか。