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

Last updated at 2024-10-19Posted at 2024-10-05

場合の数を全列挙

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

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

場合の数

#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

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

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

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

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;
  }
}

全実装です。

#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

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の数列を生成すると見ることもでき、そうすると、次のようにも書けます。

#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);
}

ここは数え上げのためのバックトラックと呼ばれる実装方式。

    A.push_back(i);
    dfs(A);
    A.pop_back();

一般にはこういう実装。

(次のノードへの遷移)
(再帰呼出し)
(一回元に戻す)

output

参考

バックトラックは数学者DHレーマーが名付けたんだそうです。
D._H._Lehmer
バックトラック
 Backtracking

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up