麻雀で学ぶアルゴリズム(1) 手牌/牌山生成(全幅)

先日このような記事を書きました。

tomohxx.hatenablog.com

Twitterで多くの人が興味をもってくれたようでうれしいです。そんなわけで麻雀をテーマにアルゴリズムを勉強していきたいと思います。

1回目のテーマは「手牌/牌山生成(全幅)」です。「全幅」の意味はすべての手牌/牌山を生成するという意味です。今回考える問題は以下のようになります。

萬子を $M$ 枚使ってできる牌の組み合わせをすべて生成せよ。

問題文の萬子には意味がなくて筒子でも索子でも字牌でもいいです。では解いていきます。 $n$ 萬の枚数を $h_n \ (1 \le n \le 9)$ とします。今 $n$ 萬の枚数を考えていて、( $n$ 萬を含め) $m$ 枚牌を使わなければならないとします。まず $n$ 萬の枚数がとりうる最大値は ${\rm min}(4, m)$ です。次に最小値を考えます。 $n$ 萬の枚数を決めた後は $4(9-n)$ 枚が未使用になっています。 $m$ がこの値より多いときはその差を最小値とする必要があります。よって $n$ 萬の枚数がとりうる最小値は ${\rm max}(0, m-4(9-n))$ です。 $n+1$ 萬の枚数については $m$ を $m-h_n$ に置き換えて同様に考えればよいです。この処理を再帰関数で実装します。添え字を1ずらしていることに注意してください。

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

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

  if(n == 9){
    callback(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, callback);
    }
  }
}

int main()
{
  int M;
  // 入力
  std::cin >> M;
  // M枚からなる組み合わせをすべて生成する
  generate(0, M, [](const std::vector<int>& h){
    // hを使った処理
    // 組み合わせを表示する例
    for(const auto& i : h){
      std::cout << i << ' ';
    }
    std::cout << '\n';
  });

  return 0;
}