シャッフルと乱数 | Programming Place Plus　新C++編

このページの概要

このページでは、配列の要素をランダムにシャッフルする方法と、そのために用いる乱数について取り上げます。また、その説明の過程の中で、関数オブジェクトについても触れています。ポーカーのようなトランプゲームでは、いつも同じカードが同じ順番に出てきては困ります。遊ぶたびに異なる展開になることを望むため、不規則にカードをシャッフルする方法が必要です。

以下は目次です。要点だけをさっと確認したい方は、「まとめ」をご覧ください。

• トランプを表現する
• シャッフル
• 関数オブジェクト
• 乱数
  • 一定範囲の乱数を得る
• まとめ
• 練習問題
• 参考リンク
• 更新履歴

トランプを表現する

ポーカーの話に戻って、トランプのカードを表現する方法を検討していきましょう。

カードの数字は、「整数型」のページで取り上げた整数型のいずれかを使って表現できます。不用意に型を混在させない方がいいという考え方に従うなら、int型を選ぶべきだということになります。一方で、数字には 1～13 しか登場しないので、メモリ使用量を節約する意義があるのなら、int型より小さい整数型を使う考え方もあります。今回はメモリ使用量を減らす道を選んで、signed char型を使うことにします。

カードのマークには列挙型（scoped enum）が使えます。こちらも、メモリ使用量を減らすために、基底型に signed char型を選ぶことにします。

カードを構造体型で表現すると、次のようになります。

// カードの数字の型
using CardNumber = signed char;

// カードのマークの型
enum class CardMark : signed char {
    spade,
    club,
    diamond,
    heart,
};

// カード型
struct Card {
    CardNumber number;  // 数字
    CardMark mark;      // マーク
};

数字の型を signed char型のまま使うと、カードの数字のことを表しているのか、ほかの意味の整数なのか分かりづらくなりますし、あとから int型の方が良かったということになるかもしれませんから、型の別名を定義しました。

トランプのすべてのカードを表現するには、std::vector が使えます（ジョーカーは除いています）。

constexpr auto trump_card_num = 52;  // トランプに含まれるカードの枚数
std::vector<Card> cards(trump_card_num);

このままだと、１枚１枚のカードは、数字が 0、マークが 0（CardMark::spade）で初期化されています。数字が 0 というカードはトランプにはありませんし、52枚全部が同じになっていることも不適切です。１枚１枚に正しい初期値を与えなければなりません。これはそこそこ面倒ですが、たとえば次のようにして実現できます。

constexpr auto each_mark_card_num = 13;  // 各マークのカードの枚数
constexpr auto trump_card_num = each_mark_card_num * 4;  // トランプに含まれるカードの枚数

// トランプを初期化する
void init_trump(std::vector<Card>& cards)
{
    for (auto i = 0; i < each_mark_card_num; ++i) {
        auto number = static_cast<CardNumber>(i + 1);
        cards.at(i + each_mark_card_num * 0).number = number;
        cards.at(i + each_mark_card_num * 0).mark = CardMark::spade;
        cards.at(i + each_mark_card_num * 1).number = number;
        cards.at(i + each_mark_card_num * 1).mark = CardMark::club;
        cards.at(i + each_mark_card_num * 2).number = number;
        cards.at(i + each_mark_card_num * 2).mark = CardMark::diamond;
        cards.at(i + each_mark_card_num * 3).number = number;
        cards.at(i + each_mark_card_num * 3).mark = CardMark::heart;
    }
}

方法は色々ありますが、ここでは各マークが 13枚ずつあることに着目して、13回まわるループを構築し、ループの中で４つのマークのカードを一気に作っています。

static_cast をしているのは、CardNumber型を signed char型の別名としているためです。i + 1 の型が int なので、signed char型への変換は暗黙的な縮小変換であり、多くのコンパイラはこれを警告します。もし、メモリ消費量を抑えるという方針を採らず、CardNumber型を int型の別名にしていれば、型変換が不要なので、static_cast も必要ありません。

プログラム全体は次のようになります。

#include <iostream>
#include <string>
#include <vector>

// カードの数字の型
using CardNumber = signed char;

// カードのマークの型
enum class CardMark : signed char {
    spade,
    club,
    diamond,
    heart,
};

// カード型
struct Card {
    CardNumber number;  // 数字
    CardMark mark;      // マーク
};

constexpr auto each_mark_card_num = 13;                  // 各マークのカードの枚数
constexpr auto trump_card_num = each_mark_card_num * 4;  // トランプに含まれるカードの枚数

// トランプを初期化する
void init_trump(std::vector<Card>& cards)
{
    for (auto i = 0; i < each_mark_card_num; ++i) {
        auto number = static_cast<CardNumber>(i + 1);
        cards.at(i + each_mark_card_num * 0).number = number;
        cards.at(i + each_mark_card_num * 0).mark = CardMark::spade;
        cards.at(i + each_mark_card_num * 1).number = number;
        cards.at(i + each_mark_card_num * 1).mark = CardMark::club;
        cards.at(i + each_mark_card_num * 2).number = number;
        cards.at(i + each_mark_card_num * 2).mark = CardMark::diamond;
        cards.at(i + each_mark_card_num * 3).number = number;
        cards.at(i + each_mark_card_num * 3).mark = CardMark::heart;
    }
}

// カードのマークの文字列表現を返す
std::string get_mark_string(CardMark card_mark)
{
    switch (card_mark) {
    case CardMark::spade:
        return "spade";
    case CardMark::club:
        return "club";
    case CardMark::diamond:
        return "diamond";
    case CardMark::heart:
        return "heart";
    default:
        return "";
    }
}

int main()
{
    std::vector<Card> cards(trump_card_num);
    init_trump(cards);

    for (auto card : cards) {
        std::cout << get_mark_string(card.mark) << " : " << static_cast<int>(card.number) << "\n";
    }
}

実行結果：

spade : 1
spade : 2
spade : 3
spade : 4
spade : 5
spade : 6
spade : 7
spade : 8
spade : 9
spade : 10
spade : 11
spade : 12
spade : 13
club : 1
club : 2
club : 3
club : 4
club : 5
club : 6
club : 7
club : 8
club : 9
club : 10
club : 11
club : 12
club : 13
diamond : 1
diamond : 2
diamond : 3
diamond : 4
diamond : 5
diamond : 6
diamond : 7
diamond : 8
diamond : 9
diamond : 10
diamond : 11
diamond : 12
diamond : 13
heart : 1
heart : 2
heart : 3
heart : 4
heart : 5
heart : 6
heart : 7
heart : 8
heart : 9
heart : 10
heart : 11
heart : 12
heart : 13

52枚のカードそれぞれが異なる数字とマークの組を持つようになりました。しかし、ポーカーのようなトランプゲームでは、最初にカードをシャッフルする必要があります。今の状態はきれいに並びすぎています。そこで次の項では、std::vector の要素をランダムにシャッフルする方法を説明します。

シャッフル

std::vector のような要素の集まりをシャッフルするには、std::shuffle関数を使うのが簡単です。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト（cpprefjp、cppreference.com）で確認してください。

【C++98/03 経験者】以前は std::random_shuffle関数を使いましたが、この関数は C++14 で非推奨になり、C++17 では削除されています。¹

std::shuffle関数は、２つのイテレータを使ってシャッフルする範囲を表現し、３つ目の実引数に、乱数生成エンジンを指定します。乱数生成エンジンについてはあとで取り上げることにして、まずは使い方だけを示します。std::shuffle関数を使うには、#include <algorithm> が必要です。

以下は、std::vector<> の変数v をシャッフルするコードです。

#include <algorithm>  // std::shuffle
#include <random>     // std::random_device、std::mt19937

std::random_device rand_dev {};
std::mt19937 rand_engine(rand_dev());
std::shuffle(std::begin(v), std::end(v), rand_engine);

std::random_device や std::mt19937 を使うために、#include <random> が必要です。

rand_dev は変数なので、rand_dev() という記述は特殊です。これは関数オブジェクトと呼ばれるもので、変数でありながら、関数であるかのように呼び出すことができます。関数オブジェクトについては、あとであらためて取り上げます。

最初のプログラムに、シャッフルのコードを付け足して確認してみます。変更するのは、main関数の中と、#include の追加だけです。実行するたびに結果が変わります。

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

// （省略。最初のプログラムと同じです）

int main()
{
    std::vector<Card> cards(trump_card_num);
    init_trump(cards);

    // カードすべてをシャッフルする
    std::random_device rand_dev {};
    std::mt19937 rand_engine(rand_dev());
    std::shuffle(std::begin(cards), std::end(cards), rand_engine);

    for (auto card : cards) {
        std::cout << get_mark_string(card.mark) << " : " << static_cast<int>(card.number) << "\n";
    }
}

実行結果：

spade : 3
club : 13
club : 6
diamond : 5
heart : 5
heart : 1
heart : 3
club : 2
heart : 9
club : 7
spade : 8
club : 10
club : 1
spade : 9
diamond : 6
heart : 10
club : 3
spade : 12
club : 9
diamond : 1
heart : 12
spade : 5
club : 12
diamond : 3
diamond : 2
heart : 11
spade : 7
club : 11
spade : 2
diamond : 8
diamond : 11
club : 8
spade : 11
diamond : 12
spade : 1
diamond : 13
club : 4
heart : 13
spade : 4
spade : 13
spade : 6
club : 5
heart : 6
spade : 10
heart : 7
diamond : 4
heart : 4
diamond : 7
diamond : 9
heart : 8
heart : 2
diamond : 10

関数オブジェクト

シャッフルのプログラムには、変数名() というかたちのコードが含まれていました。

std::random_device rand_dev {};
std::mt19937 rand_engine(rand_dev());

rand_dev() のところがそれです。これは実際に関数呼出しをしています。このように変数でありながら、関数のように振る舞うことができるものを、関数オブジェクト (function object) と呼びます。

関数オブジェクトは、型としてはクラスです。「構造体」のページで触れたように、C++ では、クラスと構造体は実質同じものです。ここまでのページでは、Ｃ言語の構造体の範疇に収まる使い方に留めてきましたが、C++ の構造体（クラス）には関数を持たせることができます。そのため、() を使った関数呼び出しの構文が実現できます。

関数オブジェクトとして機能するクラスを定義するには、最低限、次のような記述が必要です。

struct 型名 {
    戻り値の型 operator()(仮引数の並び) {
        実装
    }

    // その他、任意のメンバを記述
};

struct は class でも構いませんが、class を使うにはまだ解説していないことがいくつかあるため、ここでは struct を選ぶことにします。

operator() という変わった名前の関数を定義しています（仮引数を書くための () とは別に () が必要です）。この関数を、クラスの定義の内側に記述することで、このクラスから作られる変数が関数オブジェクトになります。関数オブジェクトに対して () を使って関数呼出しを行うと、operator() が呼び出されます。

ごく簡単な関数オブジェクトを作ってみます。

#include <iostream>

struct Greeting {
    void operator()() {
        std::cout << "Hello.\n";
    }
};

int main()
{
    Greeting greeting {};

    greeting();
    greeting();
}

実行結果：

Hello.
Hello.

Greeting は operator() を含んでおり、変数を宣言すると関数オブジェクトとして扱えます。そのため、greeting() という呼び出しによって operator() が実行されて、"Hello.\n" が出力されます。

Greeting は operator() 以外のものを含んでいませんが、クラス（構造体）なので、データメンバを持たせることもできます。たとえば、出力するメッセージを記憶するデータメンバを持たせておけば、出力内容を変更することができそうです。

operator() はその特殊な関数名のまま使うしかないので、関数名を分かりやすくして、何をおこなう関数なのか説明することができません。ヒントとなるのはむしろクラスの名前のほうです。Greeting（あいさつ）という名前があることで、その operator() があいさつをする関数であることが分かります。もし、Card構造体に operator() を持たせたとしても、それが何をするものなのかはまったく想像できないので、そのような使い方は不適切といえます。

乱数

シャッフルの処理の中には、乱数 (random number) を用いたコードが含まれています。乱数とは、規則性なくランダムに作られる数のことで、これはシャッフル以外の目的でも使えます。

std::random_device rand_dev {};
std::mt19937 rand_engine(rand_dev());
std::shuffle(std::begin(v), std::end(v), rand_engine);

このコードの中に登場する std::mt19937³ は乱数生成エンジンと呼ばれるクラスで、文字通り、乱数を生成する機能を担っています。乱数生成エンジンはいくつか種類がありますが、std::mt19937 が一般的に適切な選択になります。std::mt19937 を使うには、#include <random> が必要です。

std::mt19937 は、メルセンヌ・ツイスター（MT法）⁶と呼ばれるアルゴリズムによって乱数を生成します。mt の部分はメルセンヌ・ツイスターの略、19937 は生成される乱数の周期(2¹⁹⁹³⁷ - 1) を表しています。

【Ｃ言語プログラマー】Ｃ言語には rand関数があり、C++ にも存在しますが、C++14 からは使用が推奨されない関数になっています。rand関数がどのように実装されているかは定義されておらず、移植性や性能の面に疑いがあります⁵。

【C++98/03 経験者】古い C++ では std::rand関数を使いましたが、C++14 からは使用が推奨されない関数になっています。rand関数がどのように実装されているかは定義されておらず、移植性や性能の面に疑いがあります⁵。std::random_shuffle関数が非推奨となったのも、この関数が内部で std::rand関数を呼び出しているためです¹。

std::mt19937 には operator() が実装されているため、関数オブジェクトとして使用できます。operator() を呼び出すたびに乱数が生成されて返されます。生成される値の型は、std::uint_fast32_t（「整数型」のページを参照）で、この型で収まる範囲の整数のいずれかが得られます。

std::mt19937_64⁴ という 64ビット版のクラスも定義されており、std::uint_fast64_t型の乱数値を生成できます。64bit の整数演算が高速な環境では、こちらのほうが効率的であることが期待できます。

たとえば次のように 10回ほど繰り返し呼び出してみると、毎回異なる整数が出力されることが分かります。しかも、プログラムを実行するたびに変化します。

#include <iostream>
#include <random>

int main()
{
    std::random_device rand_dev {};
    std::mt19937 rand_engine(rand_dev());

    for (int i = 0; i < 10; ++i) {
        std::cout << rand_engine() << "\n";
    }
}

実行結果：

1051366045
494436618
3722826974
690292585
3015350657
1422399148
3787904344
1276571489
3683683735
2937580553

std::mt19937 によって得られる乱数は、疑似乱数 (pseudorandom number) と呼ばれるものです。疑似乱数は、何かしらの計算式によって数を作り出すため、計算式と最初に与えられる値を知っていれば、どんな値がどんな順番で作り出されるか予想できます。つまり、完全な意味での乱数（規則性が一切なく、次に出る数が予想できない）ではありません。

疑似乱数の計算式に与える最初の値を、シード値（乱数の種） (seed) などと呼びます。rand_engine を宣言するとき、std::mt19937 rand_engine(rand_dev()); のようにして、rand_dev() という引数を与えていますが、これがシード値です。与えたシード値が同じであれば、生成される乱数も同じになります。そのため、次のプログラムは何度実行しても同じ結果が出力されます。

#include <iostream>
#include <random>

int main()
{
    std::mt19937 rand_engine(100);

    for (int i = 0; i < 10; ++i) {
        std::cout << rand_engine() << "\n";
    }
}

実行結果：

2333906440
2882591512
1195587395
1769725799
1823289175
2260795471
3628285872
638252938
20267358
673068980

シード値を固定すれば、同じ乱数を得られるという性質が便利な場合もありますが、プログラムの実行のたびに異なる結果になってほしい場合もあります。たとえば、ポーカーのトランプが、毎回同じようにシャッフルされるのではゲームになりませんから、この場合はシード値を固定するわけにはいきません。そこで、シード値そのものを乱数にしなければなりません。乱数を作るためにシード値が必要なので、矛盾したような話ですが、これを実現するために、std::random_device⁷ を利用できます。std::random_device を使うには、#include <random> が必要です。

std::random_device rand_dev {};
std::mt19937 rand_engine(rand_dev());

std::random_device も乱数生成エンジンの一種ですが、非決定論的な乱数生成エンジンと呼ばれ、予測不可能な乱数を生成するために用意されています。ただし、処理系によっては、予測不可能な乱数を実現できない場合もあるため、std::random_device を、ほかの乱数生成エンジンを使って実装しても良いということになっています⁸。std::random_device を使っても、実際には疑似乱数による乱数生成になっている可能性があるので、事前に処理系での事情を調べておくべきです。

予測不可能な乱数が生成できるのなら、疑似乱数を使う理由などなさそうですが、std::random_device の乱数生成はかなり遅いという欠点があります。シード値を作るときのように１回使うだけならよくても、頻繁に乱数を作り出さなければならない場面で使うことは不適切です。

【上級】std::random_device が疑似乱数で実装されている場合、シード値を作るために使うのは不適切ということになります（いつも同じシード値になってしまうから、疑似乱数の生成エンジンも結局いつも同じ乱数を生成してしまう）。この場合は、現在の時刻を使うなどの別の方法を採る必要があります。

std::random_device によって得られる乱数の型は、std::random_device::result_type型で、これは unsigned int型の別名です。ただし、実際に返される可能性がある値の範囲は、min関数や max関数によって問い合わせなければ分かりません。

// いずれも std::random_device::result_type型
auto min = std::random_device::min();
auto max = std::random_device::max();

std::random_device rand_dev {};
std::mt19937 rand_engine(rand_dev());
auto result = rand_engine() % 6 + 1;  // 1～6 の範囲に収める

#include <iostream>
#include <random>

int main()
{
    std::random_device rand_dev {};
    std::mt19937 rand_engine(rand_dev());
    std::uniform_int_distribution<int> dist(1, 6);  // 1～6 を均等な確率で得る分布生成器

    for (int i = 0; i < 10; ++i) {
        std::cout << dist(rand_engine) << "\n";  // 1～6
    }
}

1
6
3
5
4
3
1
3
2
5

#include <iostream>
#include <random>

int main()
{
    std::random_device rand_dev {};
    std::mt19937 rand_engine(rand_dev());
    std::uniform_real_distribution<double> dist(0.0, 2.0);  // 0.0～2.0 を均等な確率で得る分布生成器

    for (int i = 0; i < 10; ++i) {
        std::cout << dist(rand_engine) << "\n";  // 0.0～2.0
    }
}

0.216606
1.8207
1.72469
1.91285
0.236753
1.3732
0.470071
0.817433
1.09749
1.29684

まとめ

• 配列の要素をランダムにシャッフルするために、std::shuffle関数が使える
• 変数でありながら、関数のようにも扱えるものを関数オブジェクトと呼ぶ
  • 関数オブジェクトの型はクラス（構造体）であり、operator() を実装する
• std::mt19937 は、ほとんどの用途に向いた疑似乱数生成エンジンである
  • 疑似乱数は、計算式によって乱数を作る。計算式に最初に与える値（シード値）によって生成される乱数が変化する
• std::random_device は、予測不可能な乱数を生成する（ただし、実装によっては疑似乱数である）
• 分布生成器を通すことで、生成される乱数の範囲や分布のしかたを調整できる
  • std::uniform_int_distribution や std::uniform_real_distribution は、範囲内の値が均等な確率で得られる

新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。