JavaScript で bit全探索

JavaScript で bit全探索

2019-06-1017 min read

目次

  1. 概要
  2. サンプル1
  3. サンプル2
  4. 参考

概要

AtCoderとかをやっていると、 動的計画法(DP)、部分和といった問題とかに遭遇したりしますが、1から実装しようとすると面倒だったりします。 (というよりも、再帰処理で書くのが苦手だったりするからです...) こんな時に、ビット演算を用いてパターンをひとまず網羅してから実装することがあります。 ここではJSを例に紹介します。

サンプル1

シフト演算で実装する コード

function main(n) {
  for (let bit = 0; bit < (1 << n); bit++) {
    let row = [];
    for (let i = 0; i < n; i++) {
      if (bit & (1 << i)) {
        row.push(i);
      }
    }
    console.log(row);
  }
}
main(4);

このコードの結果は次のようになります。 結果

0;
1;
0, 1;
2;
0, 2;
1, 2;
0, 1, 2;
3;
0, 3;
1, 3;
0, 1, 3;
2, 3;
0, 2, 3;
1, 2, 3;
0, 1, 2, 3;

部分和の問題を解いてみます。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

function fetchBitPattern(n, f) {
  for (let bit = 0; bit < (1 << n); bit++) {
    let row = [];
    for (let i = 0; i < n; i++) {
      if (bit & (1 << i)) {
        row.push(i);
      }
    }
    f(row);
  }
}

function main() {
  const Q = [3, 7, 8, 12, 13, 18];
  const A = 27;
  fetchBitPattern(Q.length, (bit) => {
    let s = 0;
    let tmp = [];
    for (let i = 0; i < bit.length; i++) {
      s += Q[bit[i]];
      tmp.push(Q[bit[i]]);
    }
    if (s === A) {
      console.log(tmp);
    }
  });
}

main();
[7, 8, 12];

と表示されます。

サンプル2

toStringメソッドで実装する。

function main(n) {
  for (let i = 0; i < Math.pow(2, n); i++) {
    let row = [];
    let t = i.toString(2);
    for (let j = t.length; j < n; j++) {
      t = '0' + t;
    }
    t = t.split('').map(Number);
    for (let j = 0; j < t.length; j++) {
      if (t[j] === 1) {
        row.push(j);
      }
    }
    console.log(row);
  }
}
main(4);

このコードの結果は次のようになります。

3;
2;
2, 3;
1;
1, 3;
1, 2;
1, 2, 3;
0;
0, 3;
0, 2;
0, 2, 3;
0, 1;
0, 1, 3;
0, 1, 2;
0, 1, 2, 3;

同じく部分和問題を解いてみます。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

function fetchBitPattern(n, f) {
  for (let i = 0; i < Math.pow(2, n); i++) {
    let row = [];
    let t = i.toString(2);
    for (let j = t.length; j < n; j++) {
      t = '0' + t;
    }
    t = t.split('').map(Number);
    for (let j = 0; j < t.length; j++) {
      if (t[j] === 1) {
        row.push(j);
      }
    }
    f(row);
  }
}

function main() {
  const Q = [3, 7, 8, 12, 13, 18];
  const A = 27;
  fetchBitPattern(Q.length, (bit) => {
    let s = 0;
    let tmp = [];
    for (let i = 0; i < bit.length; i++) {
      s += Q[bit[i]];
      tmp.push(Q[bit[i]]);
    }
    if (s === A) {
      console.log(tmp);
    }
  });
}

main();
[7, 8, 12];

と表示されます。

見ての通り、どちらのサンプルもをゴリゴリとループで片付けているので必ずしも効率的ではないと思います。

参考

https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361

https://ja.stackoverflow.com/questions/49702/%E3%83%93%E3%83%83%E3%83%88dp%E3%81%AE%E6%80%9D%E8%80%83%E5%9B%9E%E8%B7%AF%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6

Tags
javascript(109)
linux(54)
node.js(53)
amazon%20aws(47)
typescript(44)
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0(36)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86(30)
html5(29)
php(24)
centos(24)
python(22)
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0(21)
mac(21)
mysql(20)
canvas(19)
opencv(17)
%E9%9B%91%E8%AB%87(16)
docker(16)
wordpress(15)
atcoder(14)
apache(12)
%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92(12)
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9(12)
amazon%20s3(12)
red%20hat(12)
prisma(12)
ubuntu(11)
github(10)
git(10)
vue.js(10)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86100%E6%9C%AC%E3%83%8E%E3%83%83%E3%82%AF(10)
mariadb(10)
react(9)
aws%20cdk(9)
css3(8)
%E5%8F%AF%E8%A6%96%E5%8C%96(8)
%E5%B0%8F%E3%83%8D%E3%82%BF(8)
nestjs(8)
amazon%20lightsail(7)
next.js(7)
%E3%83%96%E3%83%AD%E3%82%B0(6)
cms(6)
oracle(6)
perl(6)
gitlab(6)
iam(5)
amazon%20ec2(5)
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93(5)
aws%20amplify(5)
curl(4)
Author
githubzennqiita
ただの備忘録です。

※外部送信に関する公表事項