手牌(牌山)生成¶

全幅¶

\(M\)枚の牌からなる手牌, すなわち\(\sum_{i=0}^8 h^n_i = M\)となるすべての\(h^n\)を生成する. 今\(h^n_i\)を考えていて, (\(i\)番目の牌を含め)\(m\)枚牌を使わなければならないとする. まず\(h^n_i\)の最大値は\({\rm min}(4, m)\)である. 次に最小値を考える. \(i\)番目の牌の枚数を決めた後は\(4(8-i)\)枚が未使用になっている. \(m\)がこの値より大きいときはその差を最小値とする必要がある. よって\(h^n_i\)の最小値は\({\rm max}(0, m-4(8-i))\)である. \(h^n_{i+1}\)については\(m\)を\(m-h^n_i\)に置き換えて同様に考えればよい. この処理を再帰関数で実装する.

#include <iostream>
#include <functional>
#include <vector>

void generate(int n, int m, std::function<void(const std::vector<int>&)> func)
{
  static std::vector<int> h(9);

  if (n == 9) {
    func(h);
  }
  else {
    for (int i = std::max(0, m - 4 * (8 - n)); i <= std::min(4, m); ++i) {
      h[n] = i;
      generate(n + 1, m - i, func);
    }
  }
}

int main()
{
  int M;

  std::cin >> M;

  generate(0, M, [](const std::vector<int>& h) {
    for (const auto& i : h) {
      std::cout << i << ' ';
    }
    std::cout << '\n';
  });

  return 0;
}

乱択¶

\(M\)枚の牌からなる手牌をランダムに\(N\)個生成する. これはFisher-Yates 法を用いて実現できる. ここでは 136 枚の牌を区別して手牌を構成する牌の番号を出力する.

#include <iostream>
#include <random>
#include <vector>

int main()
{
  int M, N;
  std::vector<int> tiles(136);
  std::mt19937 rand(std::random_device{}());

  std::cin >> M >> N;

  std::iota(tiles.begin(), tiles.end(), 0);

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      int n = rand() % (136 - j);
      std::cout << tiles[n] << " ";
      std::swap(tiles[n], tiles[135 - j]);
    }
    std::cout << "\n";
  }

  return 0;
}

Note

std::sampleの利用も検討する

重複組み合わせ¶

同じ種類の牌を区別する場合の 14 枚の手牌のパターン数は\(_{136}C_{14}\)である. 一方, 同じ種類の牌を区別しない場合のパターン数は, すべての手牌パターンを生成することでも求められるが, 重複組み合わせを考えれば高速に求められる. アルゴリズムについては『プログラミングコンテストチャレンジブック第 2 版』を参照することとし, ここではソースコードのみ示す.

#include <array>
#include <iostream>

int main()
{
  // N 種類の牌があり, それぞれの種類の牌は A 枚ずつある.
  // 異なる種類の牌同士は区別できるが, 同じ種類の牌同士は区別できない.
  // これらの牌から M 枚選ぶ組み合わせの総数を求める.

  constexpr int N = 34;
  constexpr int M = 14;
  constexpr int A = 4;

  std::array<std::array<unsigned long long, M + 1>, N + 1> dp{};

  for (int i = 0; i <= N; ++i) {
    dp[i][0] = 1;
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= M; ++j) {
      if (j - 1 - A >= 0) {
        dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - A];
      }
      else {
        dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j];
      }
    }
  }

  std::cout << dp[N][M] << std::endl;

  return 0;
}

出力:

1	`326520504500`

形式的べき級数¶

前述の手牌のパターン数は形式的べき級数を使っても求められる. ここでは多項式\(f(x)\)の\(x^n\)の係数を\([x^n]f\)と表すことにする.

赤ドラを区別しない場合¶

赤ドラを区別しない場合, 手牌のパターン数は\([x^{14}](1+x+x^2+x^3+x^4)^{33}\)である.

ソースコード:

#include <array>
#include <iostream>
constexpr unsigned int MAX_DEGREES = 14u;
using ull = unsigned long long int;
using arr = std::array<ull, MAX_DEGREES + 1u>;

arr mul(const arr& f, const arr& g)
{
  arr h = {};

  for (int i = 0; i <= MAX_DEGREES; ++i) {
    for (int j = 0; j <= MAX_DEGREES; ++j) {
      if (i + j > MAX_DEGREES) break;

      h[i + j] += f[i] * g[j];
    }
  }

  return h;
}

int main()
{
  const arr f = {1, 1, 1, 1, 1};
  auto g = f;

  for (unsigned int i = 0; i < 33; ++i) {
    g = mul(f, g);
  }

  std::cout << g[MAX_DEGREES] << std::endl;
  std::cout << g[MAX_DEGREES - 1u] << std::endl;

  return 0;
}

出力:

326520504500
98521596000

1行目は14枚(親の配牌)のパターン数, 2行目は13枚(子の配牌)のパターン数である.

赤ドラを区別する場合¶

赤ドラを区別する場合, 手牌のパターン数は\([x^{14}](1+x+x^2+x^3+x^4)^{30}(1+x+x^2+x^3)^{3}(1+x)^{3}\)である.