【C++】 unordered_mapを使用したFisher-Yates法

【C++】 unordered_mapを使用したFisher-Yates法
(2019年9月7日)


■使用ソフト
・Visual Studio Community 2019


■言語
・C/C++


■Windows SDK バージョン
・10.0.17763.0
　※Windows SDK バージョンの変更方法


■手順
１．以下をベースにコード変更する。
【C++】 メッセージボックスの作成

２．C++ファイル(.cpp)を以下のとおり変更する。

#include <windows.h>
#include <random>
#include <unordered_map>

int APIENTRY wWinMain(_In_ HINSTANCE hInstance, _In_opt_ HINSTANCE hPrevInstance, _In_ LPWSTR lpCmdLine, _In_ int nCmdShow)
{
    WCHAR wcText[256];

    int size = 5;
    int randmin = 0;
    int randmax = 9;

    std::vector<int> v;
    v.reserve(size);

    std::random_device seed;
    std::mt19937 random(seed());

    int choice;
    std::unordered_map<int, int> um;
    std::unordered_map<int, int>::iterator itr, max_itr;

    for (int i = 0; i < size; i++)
    {
        choice = std::uniform_int_distribution<int>(randmin, randmax)(random);//randmin～randmaxの中からランダムに1つ数字を選ぶ
        itr = um.find(choice);//選んだ数字がunorderd_mapの1番目の数字の中に登録されているか探す

        if (itr != um.end())//unorderd_mapの中に登録されている場合
        {
            v.push_back(itr->second);//登録されている2番目の数字をvectorに格納
        }
        else//unorderd_mapの中に登録されていない場合
        {
            v.push_back(choice);//選んだ数字をvectorに格納
        }

        if (choice != randmax)//選んだ数字がrandmaxと同じではない場合
        {
            max_itr = um.find(randmax);//randmaxがunorderd_mapの1番目の数字の中に登録さているか探す
            if (max_itr != um.end()) um[choice] = max_itr->second;//randmaxがunorderd_mapに登録されている場合、unorderd_mapに1番目：選んだ数字、2番目：randmaxの2番目の数字を格納
            else um[choice] = randmax;//randmaxがunorderd_mapに登録されていない場合、unorderd_mapに1番目：選んだ数字、2番目：randmaxを格納
        }

        randmax -= 1;//randmaxから1をマイナスする

        //--------------------------------------------------------------------------------
        //●i = 0, randmax = 9
        //　0 1 2 3 4 5 6 7 8 9
        //
        //　unorderd_map 空っぽ
        //　vector 空っぽ
        //
        //　0～9の中からランダムに1つ数字を選ぶ→4
        //　選んだ数字がunorderd_mapの1番目の数字の中に登録さているか探す→ない
        //　　選んだ数字をvectorに格納→v[0] = 4
        //　選んだ数字がrandmaxと同じでない場合→4 != 9
        //　　randmaxがunorderd_mapの1番目の数字の中に登録さているか探す→ない
        //　　unorderd_mapに1番目：選んだ数字、2番目：randmaxを格納→{4, 9}
        //　randmaxから1をマイナスする→randmax = 8
        //
        //●i = 1, randmax = 8
        //　0 1 2 3 4(9) 5 6 7 8
        //
        //　unorderd_map {4, 9}
        //　vector 4
        //
        //　0～8の中からランダムに1つ数字を選ぶ→4
        //　選んだ数字がunorderd_mapの1番目の数字の中に登録さているか探す→ある{4, 9}
        //　　登録されている2番目の数字をvectorに格納→v[1] = 9
        //　選んだ数字がrandmaxと同じではない場合→4 != 8
        //　　randmaxがunorderd_mapの1番目の数字の中に登録さているか探す→ない
        //　　unorderd_mapに1番目：選んだ数字、2番目：randmaxを格納→{4, 8}　※{4, 9}は{4, 8}に上書きされる
        //　randmaxから1をマイナスする→randmax = 7
        //
        //●i = 2, randmax = 7
        //　0 1 2 3 4(8) 5 6 7
        //
        //　unorderd_map {4, 8}
        //　vector 4, 9
        //
        //　0～7の中からランダムに1つ数字を選ぶ→6
        //　選んだ数字がunorderd_mapの1番目の数字の中に登録さているか探す→ない
        //　　選んだ数字をvectorに格納→v[2] = 6
        //　選んだ数字がrandmaxと同じではない場合→6 != 7
        //　　randmaxがunorderd_mapの1番目の数字の中に登録さているか探す→ない
        //　　unorderd_mapに1番目：選んだ数字、2番目：randmaxを格納→{6, 7}
        //　randmaxから1をマイナスする→randmax = 6
        //
        //●i = 3, randmax = 6
        //　0 1 2 3 4(8) 5 6(7)
        //
        //　unorderd_map {4, 8}, {6, 7}
        //　vector 4, 9, 6
        //
        //　0～6の中からランダムに1つ数字を選ぶ→5
        //　選んだ数字がunorderd_mapの1番目の数字の中に登録さているか探す→ない
        //　　選んだ数字をvectorに格納→v[3] = 5
        //　選んだ数字がrandmaxと同じではない場合→5 != 6
        //　　randmaxがunorderd_mapの1番目の数字の中に登録さているか探す→ある{6, 7}
        //　　unorderd_mapに1番目：選んだ数字、2番目：randmaxの2番目の数字を格納→{5, 7}
        //　randmaxから1をマイナスする→randmax = 5
        //
        //●i = 4, randmax = 5
        //　0 1 2 3 4(8) 5(7)
        //
        //　unorderd_map {4, 8}, {6, 7}, {5, 7}
        //　vector 4, 9, 6, 5
        //
        //　0～5の中からランダムに1つ数字を選ぶ→5
        //　選んだ数字がunorderd_mapの1番目の数字の中に登録さているか探す→ある{5, 7}
        //　　登録されている2番目の数字をvectorに格納→v[4] = 7
        //　選んだ数字がrandmaxと同じ→5 == 5
        //　randmaxから1をマイナスする→randmax = 4
        //
        //■最終結果（例）
        //　vector 4, 9, 6, 5, 7
    }

    swprintf(wcText, 256, L"%d %d %d %d %d", v[0], v[1], v[2], v[3], v[4]);

    MessageBox(NULL, wcText, L"unordered_mapを使用したFisher-Yates法", MB_OK);

    return 0;
}

３．実行結果（0～9までの数字をシャッフルして、最初の5文字を出力する）

４．参考文献
C++で効率よく重複のない乱数列を生成する