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

トップページ新C++編

このページの概要 🔗

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

このページの解説は C++14 をベースとしています

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



トランプを表現する 🔗

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

カードの数字は、「整数型」のページで取り上げた整数型のいずれかを使って表現できます。不用意に型を混在させない方がいいという考え方に従うなら、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);

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

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回まわるループを構築し、ループの中で4つのマークのカードを一気に作っています。

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関数を使うのが簡単です。

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

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

std::shuffle関数は、2つのイテレータを使ってシャッフルする範囲を表現し、3つ目の実引数に、乱数生成エンジンを指定します。乱数生成エンジンについてはあとで取り上げることにして、まずは使い方だけを示します。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言語の構造体の範疇に収まる使い方に留めてきましたが、C++ の構造体(クラス)には関数を持たせることができます。そのため、() を使った関数呼び出しの構文が実現できます。

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

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

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

structclass でも構いませんが、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[3] は乱数生成エンジンと呼ばれるクラスで、文字通り、乱数を生成する機能を担っています。乱数生成エンジンはいくつか種類がありますが、std::mt19937 が一般的に適切な選択になります。std::mt19937 を使うには、#include <random> が必要です。

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

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

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

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

std::mt19937_64[4] という 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[7] を利用できます。std::random_device を使うには、#include <random> が必要です。

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

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

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

【上級】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::mt19937 を使って疑似乱数を得ることはできますが、その値は std::uint_fast32_t型の範囲で返されるため、巨大な数が生成されすぎて、そのまま使うわけにはいかないことがほとんどです。たとえばサイコロを実現するために使うのなら、欲しい値は 1~6 の範囲のはずです。

1つの方法として、生成された乱数の剰余を取ったり、加算や減算をして範囲を調節したりすることが考えられます。

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

この方法は古くから実際に使われていますが、生成される結果に偏りが生じてしまい、乱数としての質が悪くなっています。

仮に、rand_engine() が返す値が 0~15 しかないとして考えてみます。0~15 の 16通りの数を、剰余と加算を駆使して 1~6 の 6通りに収めようとするので、結果が 1 になるのは 0、6、12 の 3通り、2 になるのは 1、7、13 の 3通りです。同様に 3 や 4 になるのもそれぞれ 3通りずつです。一方、結果が 5 になるのは 4、10 の 2通り、6 になるのは 5、11 の 2通りしかありません。結果に偏りが生じるというのはこういうことで、5~6 よりも、1~4 の方が出やすいサイコロになっています。

そこで、分布生成器と呼ばれるクラスを使います。分布生成器は、乱数生成エンジンが生成する乱数の範囲や分布のしかたを調整します。分布生成器も複数存在しますが、ここでは std::uniform_int_distribution[9] を使います。std::uniform_int_distribution は指定範囲内の整数が同じ確率で生成されるように制御します。std::uniform_int_distribution を使うには、#include <random> が必要です。

#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

std::uniform_int_distribution型の変数を宣言し、範囲の下限値と上限値を指定します。ここでは、1~6 の範囲にしたいので、dist(1, 6) としました。得られる乱数の型は、std::uniform_int_distribution<int> の末尾にある <int> の指定に従います。

実際に乱数を得るときには、dist(rand_engine) のように、分布生成器のほうの operator() を呼び出し、その実引数に乱数生成エンジンを渡します。


浮動小数点数の乱数が必要な場合は、std::uniform_real_distribution[10] を使います。使い方はほぼ同じです。

#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

まとめ 🔗


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


参考リンク 🔗


練習問題 🔗

問題の難易度について。

★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。

問題1 (確認★)

シード値を固定したシャッフルを実装すると、どのような結果になりますか?

解答・解説

問題2 (基本★)

-100 ~ 100 の範囲の整数をランダムに 100個生成するプログラムを作成してください。

解答・解説

問題3 (基本★)

次のように宣言された std::vector<int> から、要素をランダムに選び出して出力するプログラムを作成してください。

std::vector<int> v {7, -3, 2, 6, 0, 15, -2, 4};

解答・解説

問題4 (応用★★)

operator() を呼び出すたびに、前回よりも 1 大きい整数を返す関数オブジェクトを作ってください。初期値は使用者の側で指定できるようにします。

解答・解説

問題5 (応用★★)

ランダムな計算問題を、5問くりかえし出題するプログラムを作成してください。計算式は「整数 演算子 整数」のかたちにするものとし、整数は 1~10 の範囲、演算子は + - * / のいずれかにします。答えを入力させ、正解か不正解かを出力するようにしてください。

解答・解説

問題6 (発展★★★)

問題5のプログラムに、同じ5問に再び挑戦できるようにする機能を付け足してください。

解答・解説


解答・解説ページの先頭



更新履歴 🔗




はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る