手牌(牌山)生成¶

全幅¶

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

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

出力:

1 2	`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}$ である.