0x00 洗牌算法

對(duì)于一個(gè)N張卡片序列，最直接的最貼近等概率隨機(jī)的方法是列出全部 N! 種可能（即N的全排列），從中隨機(jī)抽取一種。顯然這種方式的復(fù)雜度難以接受，一個(gè)簡(jiǎn)單的洗牌操作無法容忍這種等待時(shí)間和對(duì)工作空間的占用。
這里使用經(jīng)典的Fisher-Yates算法，僅耗費(fèi)O(1)空間和O(n)時(shí)間完成操作:

[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 隨機(jī)數(shù)的產(chǎn)生

• 從學(xué)C的第一堂課就知道的一件事：rand()函數(shù)所產(chǎn)生的偽隨機(jī)數(shù)隨機(jī)性能很差，即使加上了seed（一般是Time）也容易出現(xiàn)問題，如短時(shí)間內(nèi)需要多次洗牌。這種情況雖然少見，但也需要加以考慮。
  MersenneTwister法看起來較為合適。

與其它已使用的偽隨機(jī)數(shù)發(fā)生器相比，產(chǎn)生隨機(jī)數(shù)的速度快、周期長(zhǎng)，可達(dá)到2^19937-1，且具有623維均勻分布的性質(zhì)，對(duì)于一般的應(yīng)用來說，足夠大了。

• 對(duì)于小黑屋來說，最多的大概是房間和事件牌了，最大也不超過70張，目前看來這樣的不重復(fù)空間已經(jīng)足夠使用了。
  嘗試一次8骰的能力檢定：
  13點(diǎn)，看起來運(yùn)氣不錯(cuò)。

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