概要
乱数 および ランダムな文字列の生成について、
整理した。
### C の rand 関数
擬似乱数を生成する関数です。
サンプルにある下記のコードを鵜呑みにすると、失敗する。
/* 乱数のシードを与える */
srand((unsigned)time(NULL));
/* 乱数を発生させる */
rand();
time 関数は、秒単位の 現在時刻です。
１秒以内に再実行すると、
同じ乱数列になる。
ランダムな文字列を作成するような用途では、
rand 関数の戻り値である
0 から RAND_MAX (32767) では扱いづらい。
0 から N までは剰余演算で求める。
rnd() ％ N
下記のような関数を用意すると、便利です。
int genRand(int min, int max)
{
static int flag;
if (flag == 0) {
srand((unsigned int)time(NULL));
rand();
flag = 1;
}
int ret = min + (int)(rand()*(max - min + 1.0)/(1.0+RAND_MAX));
return ret;
}
rand 関数は、ランダム性に問題がある。
C11 の random 関数
2011年に Cの仕様が改訂され、C11になった。
C11: A New C Standard Aiming at Safer Programming
random 関数と timespec_get 関数が追加された。
random 関数は rand 関数の問題を解消したもの。
timespec_get 関数は、
秒単位以下(マイクロ秒)の現在時刻が取得できるようしたもの。
下記のように使う。
struct timespec ts;
// 現在時刻を取得する
timespec_get(&ts, TIME_UTC);
// 乱数のシードを設定する
srandom(ts.tv_nsec ^ ts.tv_sec);
// 乱数を生成する
random();
注意
g++でコンパイルする時は、
c++17が必要。
おまけ
「c random」という検索ワードではヒットしない。
「posix random」にするとよい。
C++ の mt19937 関数
擬似乱数を生成する関数です。
名称は、メルセンヌ・ツイスタ法 (Mersenne Twister) と、
2の19937乗という周期からきている。
発案者は日本人です。
mt には 松本眞(まこと) と西村拓士(たくじ) のイニシャルという意味もこめられているらしい。
下記のように使う。
// デバイスから乱数を取得する
std::random_device rd;
// 乱数のシードを設定する
std::mt19937 mt(rd());
std::uniform_int_distribution<> rand(min, max);
// 乱数を生成する
rand( mt );
random_device
random_device クラスは、非決定論的な乱数生成エンジンである。
UNIX 系では /dev/random から値を読み取る。
非決定論的とは、擬似乱数のような規則性を持たず
予測不可能ということ。
では、どうやって生成するのか。
CPU の乱数生成器
最近のCPU は乱数生成器を内蔵している。
[Behind Intels New Random-Number Generator]
(https://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator)
CPUから乱数を読み出すことができる。
これでは不足という人向けに、
ハードウェア乱数生成器が販売されている。
[TrueRNGpro Hardware Random Number Generator]
(https://www.amazon.co.jp/TrueRNGpro-%E3%83%8F%E3%83%BC%E3%83%89%E3%82%A6%E3%82%A7%E3%82%A2%E4%B9%B1%E6%95%B0%E7%99%BA%E7%94%9F%E5%99%A8-Hardware-Random-Generator/dp/B01E2BJZ30)
/dev/random
OS が用意した乱数バイト列の擬似デバイスです。
CPU の乱数生成器などから生成する。
直接このデバイスを読み出して乱数を生成することができる。
/dev/urandomを使ってランダムなパスワードを生成する方法
ランダムな文字列を生成する
考え方はシンプルです。
乱数を使って、
文字配列から１文字を選ぶ。
char getRandomCharLower(void)
{
// 英小文字の例
const char CHARS[] = "abcdefghijklmnopqrstuvwxyz";
int index = genRand(0, (strlen(CHARS) - 1));
char c = CHARS[index];
return c;
}
char* getRandomCharsLower(int length)
{
char chars[length+1];
for(int i=0; j<length; i++){
chars[i] = etRandomCharLower();
}
return chars;
}
C++ の generate_n 関数を使う例
std::string genRandomStringLower(int length)
{
std::string text(length, '.');
generate_n(text.begin(), length, getRandomCharLower );
return text;
}
同じ文字を使わない
"aaa" "bbb" のような同じ文字が連続した文字列が生成されることがある。
これを避けるには、
文字を文字列に追加する前に、その文字が文字列に存在しているかをチェックする。
char* getRandomCharsLower(int length)
{
char chars[length+1];
chars[0] = '\n';
for(int i=0; i<length; i++)
{
while(1)
{
char c = getRandomCharLower();
// check duplicate
if ( fstrchr(chars, c) ) {
// skip
continue;
} else {
chars[i] = c;
chars[i+1] = '\0';
break;
}
}
chars[length] = '\n';
}
return chars;
}
文字列をランダムに並び替える
乱数を使って、文字を入れ替える。
shuffle(char* chars)
{
int len = strlen(chars);
for(int i = 0; i<len; i++)
{
int index1 = genRand(0, (len -1));
int index2 = genRand(0, (len-1));
// swap
char a = chars[index1];
char b = chars[index2];
chars[index1] = b;
chars[index2] = a;
}
}
C++の shuffle 関数を使う例
[C++日本語リファレンス: std::shuffle]
(https://cpprefjp.github.io/reference/algorithm/shuffle.html)
shuffle(std::string input)
{
std::random_device rd;
std::mt19937 mt(rd());
std::shuffle(input.begin(), input.end(), mt);
}
mkpasswd
LINUX のパスワード生成コマンドです。
英小文字、英大文字 英数字 特殊文字の文字数を指定して、ランダムな文字列を生成する。
expect パッケージに付随している。
MAC の場合は brew でインストールできる
中身は shell スクリプトです。
package expect5.45.4 : mkpasswd
これを C/C++ で実装する。
上記にて、英小文字のランダムな文字列は生成したので、
それに英大文字、英数字、特殊文字を追加する。
コマンドオプションは、man page を参考に、tclap を使って実装する。
[mkpasswd(1) - Linux man page]
(https://linux.die.net/man/1/mkpasswd)
Templatized C++ Command Line Parser Library
コードは github に公開した。
https://github.com/ohwada/MAC_cpp_Samples/blob/master/random/mkpasswd.cpp