タイトルの通り、2^N分2進数配列を全パターン作成するアルゴリズムを紹介します。
文章では伝わりずらいので、コードで。
例えば2^2の場合、
index.js
let list = [
[0, 0],
[0, 1],
[1, 1],
[1, 0],
];
この2進数のすべてのパターンの配列を作成するには、2^N分配列の作成が必要になります。
この配列のメリット
話は前後しますが、この2進数のすべてのパターンの配列があると何がうれしいかと言うと、N個の数値でそれぞれ異なるデータが存在する（重複OK）場合に全部を足したり引いたり、一部だけ足したり引いたり、足さなかったりの全パターンを簡単に計算することができます。
前提条件・データ説明
ではさっそく、今回は貿易を例に計算していきます。
自国日本では、A国、B国、C国と貿易取引を行っていると仮定します。
| 国 | 【輸出額】 | 【輸入額】 |
|---|---|---|
| A国 | 100億円 | 120億円 |
| B国 | 75億円 | 35億円 |
| C国 | 35億円 | 110億円 |
この際の貿易収支の全パターンを計算してきましょう。
指数計算の全パターンの計算後のイメージは以下のようになります。
index.js
let list = [
[0, 0, 0, 0, 0, 0], // A輸出フラグ、B輸出、C輸出、A輸入、B輸入、C輸入
.
.
.
[1, 1, 1, 1, 1, 1]
];
実装
それでは、以下に実際に計算のコードを記載していきます。
/**
* 2^N分の2進数全パターンを取得
* @param {number} N 指数
*/
const getAllIndexPattern = (N) => {
const ret = [];
// ループの回数が2^N
for (let i = 0; i < Math.pow(2, N); i++) {
const arr = [];
// i.toString(2)で数値を2進数に変換する
// その後左を0 padding
const str = i.toString(2).padStart(N, '0');
for (let j = 0; j < str.length; j++) {
arr.push(Number(str[j]));
}
ret.push(arr);
}
return ret;
};
これの実行結果が、以下です。（実際にDeveloper toolとかで呼び出してみてください）
今回ではNが6になります。
見切れちゃうので、lengthだけ見てみます。
ちゃんと2^6=64が出力されていることが分かります。
それではこの2進数全パターンを用いて、貿易収支の全パターンを計算します。
// 貿易収支の計算上、輸入＞輸入だと黒字、輸入＜輸入だと赤字のため、輸入にマイナスをつけている
const TRADE_LIST = [100, 75, 35, -120, -35, -110];
const allIndexPatternArr = getAllIndexPattern(6);
let result = [];
allIndexPatternArr.forEach(allIndexPattern => {
let sum = 0;
for (let i = 0; i < allIndexPattern.length; i++) {
sum += TRADE_LIST[i]*allIndexPattern[i];
}
result.push(sum);
});
// 重複削除
result = Array.from(new Set(result));
// 降順ソート
result.sort((a,b) => b - a);
実際に全部で38パターン（重複：26件）という結果になりました。
この結果、
『貿易黒字のパターンは16パターン、赤字は21パターン、どちらでもない1パターンの計38パターンが貿易収支の結果としてあり得えます。』
みたいな、解釈に使うことも可能です。
ちなみに今回Javascriptで計算しましたが、Pythonでも2^N分の2進数全パターンを取得のプログラムは書くことができ、さらにスマートにコーディングできます。
def get_all_index_pattern(n):
return [list(format(i, f'0{n}b')) for i in range(2**n)]
以上。