数学書紀

応用数学と、読書記録。

ビット配列の作成

長さ nのビット配列(ビット列)とは例えば、 n=2のとき、

 \{0, 0\}, \{0, 1\}, \{1, 0\}, \{1, 1\}

といったように、要素数 n個になるような0と1の組合せ全てにわたる集合である。(離散数学の分野では、 \mathbb{B}^nに含まれるベクトル、ということになる。この集合 \mathbb{B}の名前を何と言ったっけか…。ちなみに \mathbb{B}=\{0, 1\}である。)

 

MathematicaにはTuplesという組み込み関数が存在する。

reference.wolfram.com

Tuples[list,n]

list 中の n 個の要素からなるすべての可能な集合のリストを生成する.

 

これはべき集合を考えるときにも重要で、要素数 nの集合のべき集合を得るには、長さ nのビット列(の集合)を用意し、 i番目が1となっているような要素をもとの集合から選んでくれば、それはべき集合となる。

もっとも、Mathematicaにはべき集合を求める関数が存在しているが…。

 

ところで、C言語Javaでべき集合を求めたいとなると、このビット列の考えが必要となる。ビット列を生成するには、0から 2^nまで順に2進数変換し、桁ごとに2次元配列に組み込んでいけばよい。