LANG SELRCT

コードを書く場所についてはこちら

2018年2月14日水曜日

JavaScriptで組み合わせの数の計算をする


組み合わせの数の計算をJavaScriptで実現する

n: 個の中から
r: 個を取り出す


組み合わせの公式
  • nCr = n × (n -1) × (n -2) × ... × (n -r + 1) / r × (r - 1) × ... × 1
    = nPr / r!
    = n! / (n - r)!


例えば
アメ、チョコ、ガム の3つの選択肢があるとき
2つを取り出して
取り出した順番を見ずに
何と何が取り出されたか
その組み合わせのパターンは

アメ、チョコ = (チョコ、アメ)
アメ、ガム = (ガム 、アメ)
チョコ、ガム = (ガム 、チョコ)

の3パターンある


nPr / r! の計算でやる例

コード1.gs
function combination(){
  var n = 5;
  var r = 2;
  var numerator = permutation(n, r);
  var denominator = factorial(r);
  var result = numerator / denominator;
  Logger.log(result);  
}

function permutation(n, r) {
  var result = n;
  for(var i = 1; i < r; i++){
    result = result * (n - i)  
  }
  return result;
}

function factorial(target) {
  var result = 1;
  for(var i = 0; i < target; i++){
    var num = i + 1;
    result = result * num;
  }
  return result;
}
意訳
この機能がやること
総数を決める
取り出す数を決める
順列の結果を取得する
階乗の結果を取得する
組み合わせの公式に代入して
結果をログに出す


この機能がやること
resultの初期値を総数にしておく
取り出す数の分だけ以下を繰り返す
resultに result × (総数-i)

ログに出す


この機能がやること
結果の初期値を1にする
対象の数だけ以下を繰り返す
ひとつずつ+1して
resultに掛ける

結果をログに出す




n! / r!(n - r)! の計算でやる例

コード2.gs
function combination(){
  var n = 5;
  var r = 2;
  var numerator = factorial(n);
  var denominator = factorial(r) * factorial(n-r)
  var result = numerator / denominator;
  Logger.log(result);  
}

function factorial(target) {
  var result = 1;
  for(var i = 0; i < target; i++){
    var num = i + 1;
    result = result * num;
  }
  return result;
}
意訳
この機能がやること
総数を決める
取り出す数を決める
分子はnの階乗
分母はrの階乗×(n-r)の階乗
分子 / 分母 を計算して
ログに出す


この機能がやること
結果の初期値を1にする
対象の数だけ以下を繰り返す
ひとつずつ+1して
resultに掛ける

結果をログに出す





実行結果はコード1.gs, コード2.gsどちらも 3 になる


HTML Serviceで作る例



コード.gs
function doGet() {
  return HtmlService.createHtmlOutputFromFile("index");
}



index.html
<!DOCTYPE html>
<html>
<body>
  n:<input id="tb_n"><br>
  r:<input id="tb_r"><br>
  <button id="bt">組み合わせの数は</button>
  <input id="tb_result">
  <script>
    var tb_n = document.getElementById("tb_n");
    var tb_r = document.getElementById("tb_r");
    var tb_result = document.getElementById("tb_result");
    var bt = document.getElementById("bt");
    bt.onclick = combination;

    function combination() {
      var n = tb_n.value;
      var r = tb_r.value;
      var numerator = permutation(n, r);
      var denominator = factorial(r);
      var result = numerator / denominator;
      tb_result.value = result;
    }

    function permutation(n, r) {
      var result = n;
      for (var i = 1; i < r; i++) {
        result = result * (n - i)
      }
      return result;
    }

    function factorial(target) {
      var result = 1;
      for (var i = 0; i < target; i++) {
        var num = i + 1;
        result = result * num;
      }
      return result;
    }
  </script>
</body>
</html>