关于洗牌

首先,什么是洗牌?百度百科上的释义为:把牌搀和整理,以便继续玩。
那么,从程序的角度,我们来思考一个问题:
如何设计一个公平的洗牌算法?

简单的洗牌算法

洗牌,显然是一个随机算法。随机还不简单?随机呗。把所有牌(所有数)放到一个数组中,每次取两张牌交换位置,随机 k 次即可。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void Shuffe(int *a, int n, int k)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < k; i++)
    {
        swap(&a[rand() % n], &a[rand() % n]);
    }
}

来自HR的质疑

于是你将这段代码写给HR,认为这么简单的问题难不倒。但通常HR会进一步问:k 应该取多少?10的3次方?4次方?5次方?
很显然,取一个固定的值不合理。如果数组中有 1000000 个元素,随机 100 次太少;如果数组中只有 10 个元素,随机 10000 次又太多。一个合理的选择是,随机次数和数组中元素大小相关。比如数组有多少个元素,我们就随机多少次。
这个答案已经好很多了。但其实,连这个问题的本质都没有触及到。此时,HR一定会狡黠地一笑:这个算法公平吗?
回到问题:如何设计一个公平的洗牌算法?

公平但复杂的洗牌算法

公平——保证随机性。

其实当你开始思考这个问题时,答案不难想到。洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素,最终排列的可能性一共有 n! 个。公平的洗牌算法,应该能等概率地给出这 n! 个结果中的任意一个。
如思考到这一点,我们就能设计出一个简单的暴力算法了:对于 n 个元素,生成这 n 个元素的全排列,然后,随机抽一个。

时间复杂度

这个算法绝对是公平的。但问题是,复杂度太高!复杂度是多少呢?O(n!)。因为,n 个元素一共有 n! 种排列,我们求出所有 n! 种排列,至少需要 n! 的时间。
如果你认为这并不是什么大的复杂度,那你就错了。实际上,这是一个比指数级 O(2^n) 更高的复杂度。因为当 n>=4 开始,n! 以极快的的速度超越 2^n。
O(2^n) 已经被称为指数爆炸了,O(n!) 不可想象。
所以,这个算法确实是公平的,但是,时间不可容忍。

Knuth 洗牌算法

换个角度

我们再换一个角度思考「公平」这个话题。其实,我们也可以认为
如果:

  • 一张牌出现在任何位置的概率是相等的
  • 一个位置出现任何牌的概率是相等的

那么,我们可以认为他的随机性是可以保证的。
这个定义和上面的最终洗牌结果,可以等概率地给出这 n! 个排列中的任意一个,是等价的。

流程

  • 该算法类似于插入排序
  • 从数组的最后一个数(下标为i)开始,进行随机取余(除数为i+1,确保下标不过界)
  • 将得到的下标对应的元素和最后一个数交换
  • 将最后一个数不在视为数组中的元素,继续循环
  • 直到只剩下第一个元素为止

这个算法就是大名鼎鼎的 Knuth-Shuffle,即 Knuth 洗牌算法。

证明

  1. 很明显任何一张牌出现在第一个位置的概率都是相等的。P=1/N
    那任何一张牌出现在第二张的概率如何计算呢?首先该张牌不能出现在第一张,P=(N-1)/N;
    而后需要从N-1张牌中被选中,概率 P=((N-1)/N)*(1/(N-1))=1/N
    以此类推可以知道,任何一张牌出现在任何位置的概率是相等的。条件1证明完毕。
  2. 同样的道理
    位置1出现任何牌的概率是1/N
    位置2出现任何牌的概率同样也是((N-1)/N)*(1/(N-1))=1/N
  3. 以此类推,任何一张牌出现在任何位置的概率是相等的
    条件2证明完毕。

Knuth 何许人也?

中文名:高纳德。算法理论的创始人。我们现在所使用的各种算法复杂度分析的符号,就是他发明的。上世纪 60-70 年代计算机算法的黄金时期,近乎就是他一手主导的。他所写的《The Art of Computer Programming》,简称 TAOCP。这套书准备写七卷本,然后,到今天还没有写完,但已经被《科学美国人》评为可以媲美相对论的巨著。
比尔盖茨曾今说过,如果你看完了这套书的第一卷本,请直接给我发简历。
其他详细信息,可以自行Google。

代码

基于这个定义,我们就可以给出代码了。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int n,a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
void Print(void)
{
    for (int i=0;i<n;i++) cout<<a[i]<<' ';
    cout<<endl;
}
void swap(int *a,int *b)
{
    int c; c=*a; *a=*b; *b=c;
}
void Shuffe(void)
{
    srand((unsigned)time(NULL));
    for (int i = n - 1; i > 0; --i)     
        swap(&a[i], &a[rand() % i]);
}
int main(void)
{
    n=sizeof(a)/sizeof(int);
    while (1)
    {
        Shuffe();
        Print();
        system("pause>nul");
    }
    return 0;
}

核心代码只有两行,非常简洁。

应用

这个算法除了洗牌,还能怎么用?
其实,在很多随机的地方,都能使用。比如,扫雷生成随机的盘面。我们可以把扫雷的二维盘面先逐行连接,看作是一维的。之后,把 k 颗雷依次放在开始的位置。
然后,我们运行一遍 Knuth 洗牌算法,就可以随机摆放地雷了~

算法就像这世界一样,尽管复杂,但如此优雅。


风吟如语 樱辉坂道