いきなり答える備忘録

G Suite・Microsoft 365・LibreOfficeなどに関するメモと日々の実験

(Gスプレッドシート)ビット全探索

注:記事初出時に下記の式中で「B3^2」となっていた箇所がありましたが、いずれも「2^B3」が正解ですので訂正しました。ご指摘いただきありがとうございました。

 Googleスプレッドシートで、n 個の要素から0~n個を取り出すすべての組み合わせ(つまりすべての部分集合)をピックアップする方法についてです。

  • SEQUENCE関数やBASE関数等を組み合わせて、n個の要素から0~n個を取り出す組み合わせのすべてを列挙できます。

手順

f:id:accs2014:20210321111936p:plain:right:w500

 B3セルにビット数(n)として「4」が入力されています。
 そこでD3セルに次のような式を入力してみます。

=ARRAYFORMULA(BASE(SEQUENCE(2^B3,1,0),2,4))

 SEQUENCE関数で0から15までの16通り(2^B3=2^4通り)の数値を生成し、BASE関数で4桁の2進数に変換しています。


f:id:accs2014:20210321111940p:plain:right:w450

 結果はこうなります。
 これだけで16通りのすべての抽出パターン(1桁目から4桁目までの4つの要素について、0なら取り出さない、1なら取り出す)を網羅しているのですが、このままでは計算に使いにくいので……

 

f:id:accs2014:20210321111945p:plain:right:w550

 さらにSEQUENCE関数を使って各要素を分割してみました(ただし数値ではなく文字列になっていることに注意)。

 式は次のようになります。

=ARRAYFORMULA(MID(BASE(SEQUENCE(2^B3,1,0),2,4),SEQUENCE(1,B3),1))

 上記の式にMID関数を加え、第2引数にSEQUENCE関数を与えることで各パターンを1文字ずつ分割しています。
 

f:id:accs2014:20210321111949p:plain:right:w600

 そして、ここではさらにもう少し式を加え、抽出する要素の番号を明示しています。

 式は次のようなものです。

=ARRAYFORMULA(SEQUENCE(1,B3)*MID(BASE(SEQUENCE(2^B3,1,0),2,4),SEQUENCE(1,B3),1))

 「SEQUENCE(1,B3)」つまり「1,2,3,4」という配列と、上記の結果(行列)を「*」で結んでいます。
 これにより行列の1列目の値は1倍に、2列目の値は2倍に、……、4列目の値は4倍になるため、画像のような結果になります。


 ここではすべての組み合わせを列挙しただけですが、これを応用して「足すと10になる数値の組み合わせが存在するかどうか」といったような「条件を満たす組み合わせ」の問題をしらみつぶしに解決することが可能になります。