麻雀で学ぶアルゴリズム(2) 手牌/牌山生成(乱択)

「麻雀で学ぶアルゴリズム」の2回目です。前回記事はこちら。
tomohxx.hatenablog.com

今回の問題は以下のようになります。

牌を枚使ってできる組み合わせをランダムに組生成せよ。

この問題を解くにはFisher-Yates法を用います。詳しくは以下の説明をご覧ください。

ja.wikipedia.org

まず牌を一列に並べます。この中からランダムに一つ選んで末尾の牌と入れ替えます。そして末尾の牌を除去します。残った牌から再びランダムに一つ選び末尾の牌と入れ替え、末尾の牌を除去します。このように「牌を選び入れ替え除去する」という操作を手牌の枚数だけ繰り返します。

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

int main()
{
  // 牌の種類数
  const int K = 34;
  // 手牌の枚数
  int M;
  // 何組の手牌を生成するか
  int N;
  // 牌山
  std::vector<int> tiles(4*K);
  // 乱数生成エンジン
  std::mt19937 rand(std::random_device{}());

  // 入力
  std::cin >> M >> N;

  // 牌を初期化
  for(int i=0; i<4; ++i){
    for(int j=0; j<K; ++j){
      tiles[K*i+j] = j;
    }
  }

  for(int i=0; i<N; ++i){
    for(int j=0; j<M; ++j){
      // ランダムに牌を選択する
      int n = rand()%(4*K-j);
      // 末尾の牌と入れ替える
      std::swap(tiles[n], tiles[4*K-1-j]);
      // 牌を表示する
      std::cout << n << " ";
    }
    std::cout << "\n";
  }

  return 0;
}

実は以前まではこのコードを書く必要があったのですが、C++17以降ではsample関数を使うことでアルゴリズム部分を書く必要がなくなりました。

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
  // 牌の種類数
  const int K = 34;
  // 手牌の枚数
  int M;
  // 何組の手牌を生成するか
  int N;
  // 牌山
  std::vector<int> tiles(4*K);
  // 乱数生成エンジン
  std::mt19937 rand(std::random_device{}());

  std::cin >> M >> N;

  // 牌を初期化
  for(int i=0; i<4; ++i){
    for(int j=0; j<K; ++j){
      tiles[K*i+j] = j;
    }
  }

  for(int i=0; i<N; ++i){
    // 牌を表示する
    std::sample(tiles.begin(), tiles.end(), std::ostream_iterator<int>(std::cout, " "), M, rand);
    std::cout << "\n";
  }

  return 0;
}