bit全探索を理解する(Swift)

Swiftでの実装方法だけを知りたい方のために先にコードを示す。

let n = 3
for i in 0..<(1<<n) {
  var result: [Int] = []
  for j in 0..<n {
    if (i & (1<<j)) > 0 {
      result.append(i)
    }
  }
  // 結果出力
  result.forEach { print($0) }
}

bit全探索とは?

bit全探索は部分集合をすべて求める時などに利用できるアルゴリズムである。bit演算を用いて解を求める。

0~2の部分集合である({}, {0}, {1}, {0 1}, {2}, {0 2}, {1 2}, {0 1 2})を全て求める時などに利用できる。

仕組みを理解する

カレーに入れる野菜を決めたいとする。手元には、じゃがいも、たまねぎ、にんじんがある。入れるパターンとしては、

何も入れない
にんじん
たまねぎ
たまねぎ、にんじん
じゃがいも
じゃがいも、にんじん
じゃがいも、たまねぎ
じゃがいも、たまねぎ、にんじん

の8パターン考えられる。

次に、0を入れない、1を入れるとして2進数で表してみる(じゃがいも，たまねぎ，にんじんの順)

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

全てのパターンを2進数で表すことができた。ここで、パターンをあらわした2進数を10進数にすると上から0~7の連番になっていることがわかる。for文で回せそうな気がしてきた。

コードに落とし込む

まず連番になっていることがわかった2進数をfor文で表す。

let vegetables = ["にんじん", "たまねぎ", "じゃがいも"]
let n = vegetables.count
for i in 0..<(1<<n) { }

それぞれの野菜について入れるか入れないかの2通り考えられるため総パターン数は2の3乗(2 * 2 * 2)で8となる。1を3回左にシフトさせることで1 0 0 0となる。これを10進数にすると8である。

次にカレーに入れる野菜のindexを求める。

let vegetables = ["にんじん", "たまねぎ", "じゃがいも"]
let n = vegetables.count
for i in 0..<(1<<n) {
  var selectedIndex: [Int] = [] //入れる野菜のindex
  for j in 0..<n {
    if (i & (1<<j)) > 0 {
      selectedIndex.append(j)
    }
  }
}

i に対して、各桁が1かどうか、つまりカレーに入れることになっているかを調べるfor文とif文を追加した。これでカレーに入れる野菜のindexを求めることができる。

例として i が1、 j が0の場合を考える。 i を2進数にすると0 0 1である．1を0回左シフトして2進数にすると0 0 1である。&を計算すると0 0 1となりif文の条件を満たす。 j が1や2になると&を計算した際に0 0 0となり条件を満たさない。これでindexが0であるにんじんだけを入れるパターン2が求まった。

最後に求めた結果をわかりやすく表示させるためのコードを追加する。

let vegetables = ["にんじん", "たまねぎ", "じゃがいも"]
let n = vegetables.count
for i in 0..<(1<<n) {
  var selectedIndex: [Int] = [] //入れる野菜のindex
  for j in 0..<n {
    if (i & (1<<j)) > 0 {
      selectedIndex.append(j)
    }
  }
  print("\(i+1). ", terminator: "")
  selectedIndex.forEach { print("\(vegetables[$0]), ", terminator: "") }
  print()
}

これで以下が表示される。

1. 
2. にんじん, 
3. たまねぎ, 
4. にんじん, たまねぎ, 
5. じゃがいも, 
6. にんじん, じゃがいも, 
7. たまねぎ, じゃがいも, 
8. にんじん, たまねぎ, じゃがいも,

一般化する

最後に一般化する。

let n = 3
for i in 0..<(1<<n) {
  var result: [Int] = []
  for j in 0..<n {
    if (i & (1<<j)) > 0 {
      result.append(i)
    }
  }
  // 結果出力
  result.forEach { print($0) }
}