[C++]n個をm人に配分するときの組み合わせを全列挙する(競プロ)

数学では重複組み合わせ問題とも呼ばれるらしい.

背景

https://atcoder.jp/contests/abc268/tasks/abc268_d

この問題の回答テクニックの中に, 「_を文字列と文字列の間に入れる組み合わせを全列挙する」というものがあった.

公式解説ではDFSを使っているが, 再帰ではない方法を考えたい.

問題設定

整数n, mが入力として与えられる.

n個の飴をm人に配るときの組み合わせを全列挙してください.

配られない人がいる場合や, 飴が誰にも配られずに余る場合も考慮してください.

解説

重複組合せを理解した上で, C++ の next_permutationを利用する

next_permutationは, 配列を与えると辞書順で全列挙してくれる関数. do-whileループの中で使うのがおすすめ.

  do {
    // whileループの中でfieldの辞書順が全列挙される
  } while (next_permutation(field.begin(), field.end()));

辞書順の最後に到達した配列をnext_permutationに与えるとfalseが返り値になるのでループを抜けることができる.

なお, 予め配列はソートしておく必要がある.

解法 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  // 飴と区切り棒をfieldに定義する
  // あらかじめ昇順に並べる必要がある
  // sort(field.begin(), field.end());
  vector<int> field;
  for (int i = 0; i < n; i++) field.push_back(0);
  for (int i = 0; i < m; i++) field.push_back(1);

  do {
    // 1つの組み合わせを保存しておく配列
    vector<int> ans;

    int candy_num = 0;
    for (int i = 0; i < field.size(); i++) {
      if (field[i] == 0) candy_num++;
      // 区切り棒が来たらその人は終了
      if (field[i] == 1) {
        ans.push_back(candy_num);
        candy_num = 0;
      }
    }
    ans.push_back(candy_num);

    // 1つの組み合わせを出力
    for (int i = 0; i < ans.size() - 1; i++) {
      cout << ans[i] << " ";
    }
    cout << endl;
  } while (next_permutation(field.begin(), field.end()));
}

入力

3個の飴を2人に配る

3 2

出力

例えば3 0はそれぞれ3個と0個飴をあげることを表す