0x00 洗牌算法
对于一个N张卡片序列，最直接的最贴近等概率随机的方法是列出全部 N! 种可能（即N的全排列），从中随机抽取一种。显然这种方式的复杂度难以接受，一个简单的洗牌操作无法容忍这种等待时间和对工作空间的占用。
这里使用经典的Fisher-Yates算法，仅耗费O(1)空间和O(n)时间完成操作:
[Algorithm]
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
[C]
void Shuffle_FisherYates(char *arr, const int len)
{
for(int i = len - 1; i > 0; i--)
{
int a = rand()%(i + 1);
int temp = arr[i];
arr[i] = arr[a];
arr[a] = temp;
}
}
0x01 随机数的产生
- 从学C的第一堂课就知道的一件事：rand()函数所产生的伪随机数随机性能很差，即使加上了seed（一般是Time）也容易出现问题，如短时间内需要多次洗牌。这种情况虽然少见，但也需要加以考虑。
MersenneTwister法看起来较为合适。
与其它已使用的伪随机数发生器相比，产生随机数的速度快、周期长，可达到2^19937-1，且具有623维均匀分布的性质，对于一般的应用来说，足够大了。
- 对于小黑屋来说，最多的大概是房间和事件牌了，最大也不超过70张，目前看来这样的不重复空间已经足够使用了。
尝试一次8骰的能力检定：
13点，看起来运气不错。
image.png
#ifndef _MersenneTwister_H_
#define _MersenneTwister_H_
#include <ctime>
#include <stdint.h>
#include <math.h>
using namespace std;
typedef int32_t MS_INT;
class MersenneTwister
{
public:
void rseed(MS_INT seed) {
if (isInitialized) {
return;
}
msInit(seed);
}
int rand(void) {
if (isInitialized == false) {
return 0;
}
return msRand();
}
public:
MersenneTwister(int seed) :isInitialized(0) {
rseed(seed);
}
~MersenneTwister() {
}
/* Initialize the generator from a seed */
void msInit(int seed) {
MS_INT i;
MS_INT p;
idx = 0;
MT[0] = seed;
for (i = 1; i < 624; ++i) { /* loop over each other element */
p = 1812433253 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i;
MT[i] = p & 0xffffffff; /* get last 32 bits of p */
}
isInitialized = 1;
}
/* Extract a tempered pseudorandom number based on the idx-th value,
calling ms_generate() every 624 numbers */
MS_INT msRand() {
if (!isInitialized)
msInit((MS_INT)time(NULL));
if (idx == 0)
msGenerate();
MS_INT y = MT[idx];
y = y ^ (y >> 11);
y = y ^ ((y << 7) & 2636928640);
y = y ^ ((y << 15) & 4022730752);
y = y ^ (y >> 18);
idx = (idx + 1) % 624; /* increment idx mod 624*/
return y;
}
/* Generate an array of 624 untempered numbers */
void msGenerate() {
MS_INT i, y;
for (i = 0; i < 624; ++i) {
y = (MT[i] & 0x80000000) +
(MT[(i + 1) % 624] & 0x7fffffff);
MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
if (y % 2) { /* y is odd */
MT[i] = MT[i] ^ (2567483615);
}
}
}
private:
MS_INT MT[624];
MS_INT idx;
MS_INT isInitialized;
};
#endif
