如何洗牌?

如何洗牌能足够随机呢?

之前一直想要实现一个三国杀之类的东西,然而在第一部如何洗牌里就被绊住了,横竖想了很久也想不到怎么做到从牌堆里抽牌同时还不会出现重复的牌这样的效果。

后来weng神讲了一个非常简单的做法,给每一个牌一个随机数然后再快排不就行了么?好主意啊!

但是写三国杀这个事还是就这样搁置了。主要是没有想好到底用什么语言写,以及牌与武将的扩展的方式之类的东西。而且因为对三国杀不是很热衷,所以搁置就搁置吧。

后来看到了这篇博文《如何测试洗牌程序》,突然发现洗牌好像不是那么简单,尤其是里面提出的统计意义的问题,(虽然感觉对于洗牌来说并不需要洗得多么统计独立、概率完全相等)。

但是没有道理快排的方式不对啊?默默地认为是他把compare的结果弄成了三种(-1,0,+1),而实际中0的可能性是非常小的。

于是改了一下Compare(部分代码见下),然后被怒打脸QAQ.

int compare(const char *a, const char *b){
    return rand()%2*2-1;
}

void ShuffleArray_Sort(char* arr, int len){
    qsort( (void *)arr, (size_t)len, sizeof(char), compare );
}

结果如下:

     10569     10792      9221      7989      8252     15491      3701      4518      8399     21068
     15278     16864     10119      5500      3441      5650      8083     11607     15220      8238
      8279      8458     18615     10973      6807      9333     10112     11131     10737      5555
      6101      5334      7385     23766     13087     11801     10535     10063      8296      3632
      4315      4110      5934      9614     33628     14957     11391      8173      4956      2922
     10034     10521      9336      8014      8475     16332      4043      4504      7269     21472
      6455      6361      8695      8186      8018      7159     32410     12293      6805      3618
      8577      8795      9103      8899      6882      4575     11045     25578     10660      5886
     11330     11649      9986      8185      4662      2883      6242      8929     22383     13751
     19062     17116     11606      8874      6748     11819      2438      3204      5275     13858

这到底是为什么呢?难道是伪随机数生成的有问题?还是别的?莫非是因为并没有给每一个数赋值而是直接比较导致了问题出现? 因为可能出现A>B, B>C, C>A这样的现象?(出现这种现象竟然都能排出顺序来呵呵← ←)

于是重写了一遍,并且效果好了很多~~


char weight[10];

int compare(const char *a, const char *b){
    return weight[*a]-weight[*b];
}

void ShuffleArray_Sort(char* arr, int len){
    for (int j = 0; j < 10; ++j){
        weight[j] = rand();
    }
    qsort( (void *)arr, (size_t)len, sizeof(char), compare );
}

结果:

      9958     10008     10054     10031      9892      9960     10022      9994      9963     10118
     10134      9862      9870      9927     10055     10008     10112     10017      9938     10077
     10006     10113      9821      9867     10114      9991     10003     10017      9894     10174
     10113      9987     10070      9842      9999      9800      9927      9950     10022     10290
     10043     10049     10073     10112      9844      9745      9882     10204     10060      9988
      9753     10037     10113      9884      9961     10427      9963      9875     10290      9697
      9995      9942      9926     10258     10029     10100     10064      9938      9703     10045
     10133      9942     10015     10021     10133      9916     10160      9882      9848      9950
      9966      9915     10075     10094      9888      9893     10031     10243      9985      9910
      9899     10145      9983      9964     10085     10160      9836      9880     10297      9751

事实证明我的猜测是对的,必须一开始就有一个确切的随机的顺序,然后才能保证快排以后的随机性。

源码:

最后附上概率论老师张真人的一句话:

排序是逆天行为


文章标题:如何洗牌?

文章字数:3033

本文作者:Mickir

发布时间:2016-03-08

最后更新:2017-12-06

原始链接: https://mickir.me/blog/xipai.html

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。