いきなり答える備忘録

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

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

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

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

手順

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

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

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

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


f:id:accs2014:20200704170817p:plain:right:w400

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

 

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

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

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

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

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

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

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

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

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

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


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