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