アルゴリズムの勉強(5)

異性体の問題

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

const C = 17;
const L = 2558;
let size = Array(L);
let _length = Array(L);
let count = Array(C + 1);
for (let i = 0; i < L; ++i) { size[i] = 0; }
for (let i = 0; i < L; ++i) { _length[i] = 0; }
for (let i = 0; i < C+1; ++i) { count[i] = 0; }

let i, j, k, h, len, n, si, sj, sk, sh;

n = size[0] = _length[0] = 0;
for (i = 0; i < L; ++i) {
  len = _length[i] + 1; if (len > C / 2) break;
  si = size[i] + 1; if (si + len > C) continue;
  for (j = 0; j <= i; ++j) {
    sj = si + size[j]; if (sj + len > C) continue;
    for (k = 0; k <= j; ++k) {
      sk = sj + size[k]; if (sk + len > C) continue;
      if (++n >= L) { console.log("failed"); }
      size[n] = sk; _length[n] = len;
    }
  }
}
if (len <= C / 2) { console.log("failed"); }
for (i = 0; i <= n; i++) {
  si = size[i];
  for (j = 0; j <= i; j++) {
    if (_length[i] != _length[j]) continue;
    sj = si + size[j]; if (sj > C) continue;
    count[sj]++;
    for (k = 0; k <= j; ++k) {
      sk = sj + size[k] + 1; if (sk > C) continue;
      for (h = 0; h <= k; ++h) {
        sh = sk + size[h];
        if (sh <= C) { count[sh]++; }
      }
    }
  }
}
for (i = 1; i <= C; i++) {
  console.log("炭素原子が", i, "個のものは", count[i], "種類");
}

実行結果

$ tsc isomer.ts && node isomer.js 
炭素原子が 1 個のものは 1 種類
炭素原子が 2 個のものは 1 種類
炭素原子が 3 個のものは 1 種類
炭素原子が 4 個のものは 2 種類
炭素原子が 5 個のものは 3 種類
炭素原子が 6 個のものは 5 種類
炭素原子が 7 個のものは 9 種類
炭素原子が 8 個のものは 18 種類
炭素原子が 9 個のものは 35 種類
炭素原子が 10 個のものは 75 種類
炭素原子が 11 個のものは 159 種類
炭素原子が 12 個のものは 355 種類
炭素原子が 13 個のものは 802 種類
炭素原子が 14 個のものは 1858 種類
炭素原子が 15 個のものは 4347 種類
炭素原子が 16 個のものは 10359 種類
炭素原子が 17 個のものは 24894 種類

所感

ループが3重だったり4重だったりして、計算量が多め。 コードを写経していてクラスが使いたくなった逸品。

別の言語で写すと無理がでるので、そういうアルゴリズムはスキップ。