【Python】bit全探索の基本|リストの全部分集合を求める

python

この記事では、AtCoderの解法によくあるbit全探索の解説をしています。

bit全探索でリストの全部分集合を求める

bit全探索

以下のようなリストの全部分集合を求めます。

この時、それぞれの要素に対して、「選択する」or「選択しない」の二択が考えられます。

したがって、全部分集合の総数は 2(要素数) となります。

bit全探索では、これを2進数で表し、bit演算することで全部分集合を列挙していきます。

C B A 10進数
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7

 

このように「0➡選択しない」、「1➡選択する」とすることで、2進数ですべての部分集合を表すことができます。

これを、pythonで実装し、全部分集合を表示させると以下のようになります。

出力

bit演算

上のコードの解説です。

この部分では、iを2進数で表した時のjケタ目(一番右端が0ケタ目)が1であるかどうかで場合分けしています。

例えば、i = 3, j = 1のときは下のようになります。

したがって、

となります。

例題

AtCoderのABC147( C – HonestOrUnkind2 )を解いてみます。

N人の人それぞれの証言に基づいて、正直者の最大数を出力させる問題です。

N人の人それぞれに対して「正直もの」か、「正直者でないか」の二択になるので、2N通りのパターンを一つずつ確かめていきます。

タイトルとURLをコピーしました