【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++で効率よく重複のない乱数列を生成する
