[tips][cpp][ProblemSolver] 場合の数を全列挙

# 場合の数を全列挙

ボールにはそれぞれ番号がついています。
5個の区別あるボールの数を選ぶ選び方を全列挙します。

各ボールを選ぶか選ばないで2^5(=32)通りです。次の実装で、`1 << 5`は1を左に5回ビットシフトしています。`2^5`のことです。`choose`には選び方の情報が入っています。


## 場合の数

```cpp
#include <bitset>
#include <iostream>
using namespace std;

// 5個の区別あるボールから、選ぶ選び方を全て列挙します。
int number_of_cases(int n) {
  int sum = 0;

  for (int choose = 0; choose < (1 << n); ++choose) {
    bitset<5> b(choose);
    cout << b << endl;
    sum = choose;
  }

  return sum;
}

int main() {
  int sum = number_of_cases(5);
  // undo　0-indexed
  cout << "場合の数=" << sum + 1 << endl;
}
```

output
```cpp
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
場合の数=32
```

一つも選ばない場合から、全てを選ぶ場合まで32通りです。

## 選んだか選ばないか調べる

n bitの2進数のフラグが立っているか調べます。

```cpp
void get_choice(int n, int choose) {
  vector<int> choice_item;
  for (int i = 0; i < n; i++) {
    if (choose >> i & 1) {
      choice_item.push_back(i + 1);
    }
  }

  for (int c : choice_item) {
    cout << c << "番目のボールを選びました" << endl;
  }
}
```

全実装です。
```cpp
#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

void get_choice(int n, int choose) {
  vector<int> choice_item;
  for (int i = 0; i < n; i++) {
    if (choose >> i & 1) {
      choice_item.push_back(i + 1);
    }
  }

  for (int c : choice_item) {
    cout << c << "番目のボールを選びました" << endl;
  }
}

// 5個の区別あるボールから、選ぶ選び方を全て列挙します。
int number_of_cases(int n) {
  int sum = 0;

  for (int choose = 0; choose < (1 << n); ++choose) {
    bitset<5> b(choose);
    cout << b << endl;
    sum = choose;
    get_choice(n, choose);
    cout << "----" << endl;
  }

  return sum;
}

int main() {
  int sum = number_of_cases(5);
  // undo　0-indexed
  cout << "場合の数=" << sum + 1 << endl;
}
```

output
```cpp
00000
----
00001
1番目のボールを選びました
----
00010
2番目のボールを選びました
----
00011
1番目のボールを選びました
2番目のボールを選びました
----
00100
3番目のボールを選びました
----
00101
1番目のボールを選びました
3番目のボールを選びました
----
00110
2番目のボールを選びました
3番目のボールを選びました
----
00111
1番目のボールを選びました
2番目のボールを選びました
3番目のボールを選びました
----
01000
4番目のボールを選びました
----
01001
1番目のボールを選びました
4番目のボールを選びました
----
01010
2番目のボールを選びました
4番目のボールを選びました
----
01011
1番目のボールを選びました
2番目のボールを選びました
4番目のボールを選びました
----
01100
3番目のボールを選びました
4番目のボールを選びました
----
01101
1番目のボールを選びました
3番目のボールを選びました
4番目のボールを選びました
----
01110
2番目のボールを選びました
3番目のボールを選びました
4番目のボールを選びました
----
01111
1番目のボールを選びました
2番目のボールを選びました
3番目のボールを選びました
4番目のボールを選びました
----
10000
5番目のボールを選びました
----
10001
1番目のボールを選びました
5番目のボールを選びました
----
10010
2番目のボールを選びました
5番目のボールを選びました
----
10011
1番目のボールを選びました
2番目のボールを選びました
5番目のボールを選びました
----
10100
3番目のボールを選びました
5番目のボールを選びました
----
10101
1番目のボールを選びました
3番目のボールを選びました
5番目のボールを選びました
----
10110
2番目のボールを選びました
3番目のボールを選びました
5番目のボールを選びました
----
10111
1番目のボールを選びました
2番目のボールを選びました
3番目のボールを選びました
5番目のボールを選びました
----
11000
4番目のボールを選びました
5番目のボールを選びました
----
11001
1番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
11010
2番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
11011
1番目のボールを選びました
2番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
11100
3番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
11101
1番目のボールを選びました
3番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
11110
2番目のボールを選びました
3番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
11111
1番目のボールを選びました
2番目のボールを選びました
3番目のボールを選びました
4番目のボールを選びました
5番目のボールを選びました
----
場合の数=32
```

## 補足

深さ優先探索で実装できます。

`M={0, 1}`のいずれかからなる、長さ`N=5`の数列を生成すると見ることもでき、そうすると、次のようにも書けます。

```cpp
#include <iostream>
#include <vector>
using namespace std;

int M = 2;
int N = 5;
void dfs(vector<int> &A) {
  if (A.size() == N) {
    for (int i = 0; i < N; i++)
      cout << A[i];
    cout << endl;

    return;
  }
  for (int i = 0; i < M; i++) {
    A.push_back(i);
    dfs(A);
    A.pop_back();
  }

  return;
}

int main() {
  vector<int> A;
  dfs(A);
}
```

ここは数え上げのためのバックトラックと呼ばれる実装方式。
```cpp
    A.push_back(i);
    dfs(A);
    A.pop_back();
```
一般にはこういう実装。
```
(次のノードへの遷移)
(再帰呼出し)
(一回元に戻す)
```


output
```cpp
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
```

# 参考

バックトラックは数学者DHレーマーが名付けたんだそうです。
[D._H._Lehmer](https://en.wikipedia.org/wiki/D._H._Lehmer)
[バックトラック](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AF%E3%83%88%E3%83%A9%E3%83%83%E3%82%AF)
[Backtracking](https://en.wikipedia.org/wiki/Backtracking)