ビット全探索

ビット全探索とは、二進数とビットを用いて、ある集合の部分集合を全列挙（全探索）するアルゴリズムのこと。

public class Blog {
	public static void main(String[] args) {
		//集合
		String[] ar = {"a","b","c"};
		
		//要素数
		int n = 3;
		
		//以下メイン処理
		for (int i=0; i<(Math.pow(2,n)); i++) {
			String s = "-";
			for (int j=0; j<n; j++) {
				if ((1&i>>j) == 1) {s += ar[j];}
			}
			System.out.println(s);
		}
		
		/*出力
		
		-
		-a
		-b
		-ab
		-c
		-ac
		-bc
		-abc
		
		*/
	}
}

上から順に見ていく。まず、外側のforの条件式について。

for (int i=0; i<(1<<n); i++) {};

「1<<n」の部分は、集合（ここではa,b,c）の部分集合（a,ac,abcなど）が何種類あるか、つまりこれから全探索することになる部分集合の個数を表している。「1<<n」の意味は「1をnだけ左にビットシフトする」であり、要は「2のn乗」である。よって、「1<<n」の部分は「Math.pow(2,n)」と書いてもよい。今回は集合の要素数が3個なので、その部分集合の数は（空集合を含めて）2^3=8となり、外側のループは8回まわる。

次に、内側のループのif文について。

if ((1 & i>>j) == 1) {};

この条件の意味は、「二進数iをjだけ右にビットシフトしたときの、iの1桁目と1とでビット論理積をとって、演算結果が1であるなら処理を実行する」というものである。ビット論理積は、二つのビットを比較して、両方とも1であれば1、それ以外は0を返す演算のこと。

外側のループを回していくと、iの値は

・000　-(空集合)
・001　-a
・010　-b
・011　-ab
・100　-c
・101　-ac
・110　-bc
・111　-abc

と変化する。右側は出力された部分集合である。ここでは便宜上、桁数を合わせるために0を先頭に付け足している。

iの値をよく見てみると、1桁目が配列の0番目、2桁目が配列の1番目、3桁目が配列の2番目の要素に対応していることが分かる。

より視覚的に分かりやすくするため、iの値を逆にしてみると……

・000　___
・100　a__
・010　_b_
・110　ab_
・001　__c
・101　a_c
・011　_bc
・111　abc

とこんなふうに、iの値のビットの立っている部分（1の部分）が、そのまま部分集合となっているのが分かる。

以上をまとめると、ビット全探索とは、まず集合に含まれる部分集合の数だけ二進数を0から順にピックアップし、その二進数の各桁のビットが立っているかどうかを条件式で判断し、立っている桁に対応する要素を（ピックアップした二進数の）部分集合とするアルゴリズム……ということになると思う。

ビット全探索で解くことのできる問題として、以下をあげておく。

例題1：C: たくさんの数式 / Many Formulas - AtCoder Beginner Contest 045 | AtCoder
解説1：この問題では、n桁の数字が与えられ、数字と数字のあいだに最大でn-1個の"+"を入れることができ、その入れかたのパターンを、今回紹介したbit全探索で列挙することができる。

例題2：#239883 No.617 Nafmo、買い出しに行く - yukicoder
解説2：いわゆるナップサック問題。本来はビット全探索では時間がかかりすぎるのだが、この問題では価値の概念がなく重さだけで選ぶのに加え、商品の数が最大でも20と小さいので、ビット全探索で解くことができる。

例題3：C - Train Ticket
解説3：例題1が解ければこれも解けると思う。ただしこちらは要素の数が3個（組み合わせは2^3で8通り）と少ないので、解説ページにもあるようにビット全探索を使わなくても解ける。

ビット全探索のほかにも、再帰関数を用いて同様に全列挙することも可能らしい。いずれは記事にしたい。