随机洗牌算法

前两天被问到一个随机洗牌的问题，当时脑子里想这不很简单么，生成随机数列嘛。回来之后自己动手实现了出来，然后也测试了一番，也上网搜索了一下关于随机洗牌的算法，发现现实好像不是那么简单，有一个地方容易形成误区，所以把这些记录下来。

这个误区已经有人很专业地分析过了，如下方：http://www.matrix67.com/blog/archives/879

    记得当年搞NOIp时，我犯过一个相当严重的错误：错误地把Floyd算法的i, j, k三层循环的位置顺序搞颠倒了。直到准备省选时我才突然意识到，Floyd算法应该最先枚举用于松驰操作的那个“中间变量”k，表示只经过从1到k的顶点的最短路；而我却一直习惯性地以为i, j, k应该顺次枚举。令人惊讶的是，这个错误跟了我那么久我居然从来都没有注意到过。后来，我发现有我这种经历的人不止一个。惯性思维很可能会让你接受一些明显错误的算法，并且让你用得坦坦荡荡，一辈子也发觉不了。
    假使你需要把一个数组随机打乱顺序进行重排。你需要保证重排后的结果是概率均等、完全随机的。下面两种算法哪一种是正确的？其中，random(a,b)函数用于返回一个从a到b（包括a和b）的随机整数。

1. for i:=1 to n do swap(a[i], a[random(1,n)]);
2. for i:=1 to n do swap(a[i], a[random(i,n)]);

    如果不仔细思考的话，绝大多数人会认为第一个算法才是真正随机的，因为它的操作“更对称”，保证了概率均等。但静下心来仔细思考，你会发现第二种算法才是真正满足随机性的。为了证明这一点，只需要注意到算法的本质是“随机确定a[1]的值，然后递归地对后n-1位进行操作”，用数学归纳法即可轻易说明算法的正确性。而事实上，这段程序一共将会产生n*(n-1)*(n-2)*...*1种等可能的情况，它们正好与1至n的n!种排列一一对应。
     有人会问，那第一种算法为什么就错了呢？看它的样子多么对称美观啊……且慢，我还没说第一种算法是错的哦！虽然第一种算法将产生比第二种算法更多的可能性，会导致一些重复的数列，但完全有可能每种数列重复了相同的次数，概率仍然是均等的。事实上，更有可能发生的是，这两种算法都是正确的，不过相比之下呢第一种算法显得更加对称美观一些。为此，我们需要说明，第一种算法产生的所有情况均等地分成了n!个等价的结果。显然，这个算法将会产生n^n种情况，而我们的排列一共有n!个，因此n^n必须能够被n!整除才行（否则就不能均等地分布了）。但是，n!里含有所有不超过n的质数，而n^n里却只有n的那几个质因子。这表明要想n^n能被n!整除，n的质因子中必须含有所有不超过n的质数。这个结论看上去相当荒唐，反例遍地都是，并且直觉上告诉我们对于所有大于2的n这都是不成立的。为了证明这一点，只需要注意到2是质数，并且根据Bertrand-Chebyshev定理，在n/2和n之间一定还有一个质数。这两个质数的乘积已经大于n了。搞了半天，第一种看似对称而美观的算法居然是错的！

我先写了一个测试程序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.IO;

namespace Learning.useful.tool
{
    class testWashCard
    {
        private ArrayList appearTimes = new ArrayList();
        private int cardCount;
        public int CardCount
        {
            get { return cardCount; }
            set { cardCount = value; }
        }
        private washCards algorithm;        // 洗牌算法接口 [9/9/2013 Administrator]
        public Learning.useful.tool.washCards Algorithm
        {
            get { return algorithm; }
            set { algorithm = value; }
        }
        private int testTimes;
        public int TestTimes
        {
            get { return testTimes; }
            set { testTimes = value; }
        }
        public testWashCard( int cardsCount = 10, int testTimes = 1000 )
        {
            CardCount = cardsCount;
            TestTimes = testTimes;
        }
        
        public void runTest()
        {
            if (algorithm == null)
            {
                throw new Exception("algorithm haven't been set yet!");
            }
            appearTimes.Clear();
            for (int i = 0; i < CardCount * CardCount; ++i )
            {
                appearTimes.Add(0);
            }
            FileStream fs = new FileStream("record.txt", FileMode.Create);
            StreamWriter sw = new StreamWriter(fs);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < testTimes; ++i )
            {
                System.Threading.Thread.Sleep(1);
                long tick = DateTime.Now.Ticks;
                Random ran = new Random((int)(tick & 0xffffffffL) | (int)(tick >> 32));
                ArrayList result = algorithm.washCards(CardCount, ran);         //随机洗牌测试
                for (int cardIndex = 0; cardIndex < CardCount; ++cardIndex )
                {
                    int listIndex = cardIndex * CardCount + (int)result[cardIndex];
                    appearTimes[listIndex] = (int)appearTimes[listIndex] + 1;            //统计每张牌的随机位置
                }
                sb.Clear();
                for (int index = 0; index < result.Count; ++index )
                {
                    sb.AppendFormat("{0}	", result[index]);
                }
                sw.WriteLine(sb.ToString());            //把过程记录到record.txt文件中
            }
            sw.Flush();
            sw.Close();
            fs.Close();
            showResult();
        }
        private void showResult()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < CardCount; ++i )
            {
                sb.AppendFormat("{0}	", i+1);
            }
            Console.WriteLine(sb.ToString());
            sb.Clear();
            double average = 0;
            FileStream fs = new FileStream("result.txt", FileMode.Create);
            StreamWriter sw = new StreamWriter(fs);
            for (int x = 0, y = 0; x * CardCount + y < appearTimes.Count; ++x)
            {
                sb.AppendFormat("{0}	", appearTimes[x * CardCount + y]);
                average += (int)appearTimes[x * CardCount + y];
                if (x == CardCount - 1)
                {
                    x = -1;
                    y++;
                    Console.WriteLine(sb.ToString());
                    sw.WriteLine(sb.ToString());            //把测试结果记录到result.txt文件中去
                    sb.Clear();
                }
            }
            sw.Flush();
            sw.Close();
            fs.Close();
            average /= appearTimes.Count;
            double s = 0;
            double deviation = 0;
            for (int i = 0; i < appearTimes.Count; ++i)
            {
                s += Math.Pow(average - (int)appearTimes[i], 2);
                double tmp = ((int)appearTimes[i] - average);
                deviation = tmp > deviation ? tmp : deviation;
            }
            s /= appearTimes.Count;
            Console.WriteLine("方差是：{0}", s);
            Console.WriteLine("最大误差是：{0}", deviation / average);
        }
    }
}

最开始是想通过计算方差来判断测试的结果，方差是衡量离散程度的，但是用于衡量这个测试结果不太适用。后来加上了最大误差的判断，就适合多了。

再贴上我自己的错误算法

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Learning.useful.tool
{
    class MyWashCardAlgorithm : washCards
    {

        private ArrayList randomValue = new ArrayList();
        private ArrayList result = new ArrayList();
        public ArrayList washCards(int cardCount, Random ran)
        {
            randomValue.Clear();
            result.Clear();
            
            for (int i = 0; i < cardCount; ++i )
            {
                randomValue.Add(ran.Next(0, cardCount));　　　　// 问题就出在这里，ran的范围
                result.Add(i);
            }
            sortRandomValue();
            return result;
        }
        private void sortRandomValue()
        {
            /// <summary>
            ///  快速排序
            /// </summary>
            /// 
            quickSort(0, result.Count-1);
        }

        private void quickSort(int head, int tail)
        {
            if (head >= tail)
            {
                return;
            }
            int mid = (int)randomValue[head];
            int midIndex = (int)result[head];
            int p = head;
            int q = head + 1;
            for (; q <= tail; q++)
            {
                if ((int)randomValue[q] < mid)
                {
                    randomValue[p] = randomValue[q];
                    result[p] = result[q];
                    p++;
                    randomValue[q] = randomValue[p];
                    result[q] = result[p];
                }
            }
            randomValue[p] = mid;
            result[p] = midIndex;
            quickSort(head, p - 1);
            quickSort(p + 1, tail);
        }
    }
}

以及正确的算法：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Learning.useful.tool
{
    class coolShellWashCardAlgorithm : washCards
    {

        private ArrayList randomValue = new ArrayList();
        private ArrayList result = new ArrayList();

        public ArrayList washCards(int cardCount, Random ran)
        {
            randomValue.Clear();
            result.Clear();
            for (int i = 0; i < cardCount; ++i )
            {
                result.Add(i);
            }
            ShuffleArray_Fisher_Yates(result, ran);
            return result;
        }

        private void ShuffleArray_Fisher_Yates(ArrayList arr, Random ran)
        {
            int i = arr.Count, j;
            int temp;

            if (i == 0) return;
            while (--i > 0)
            {
                j = ran.Next(i + 1);
                temp = (int)arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

两个算法的运行结果如上图。