`

随机洗牌:哪一种算法是正确的?

 
阅读更多

原文

记得当年搞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了。搞了半天,第一种看似对称而美观的算法居然是错的!

分享到:
评论

相关推荐

    洗牌算法整理

    【洗牌算法】是计算机科学中用于生成等概率随机序列的一种方法,常见于各种需要随机化元素顺序的场景,如游戏、模拟等。洗牌算法的主要目标是确保原数组中的每个元素在打乱后都有相等的概率出现在序列的任何位置。 ...

    斗地主洗牌发牌算法

    3. **优化洗牌算法**:虽然Collections.shuffle()已经足够随机,但也可以通过自定义随机数生成器或者Fisher-Yates(Knuth)洗牌算法来进一步理解洗牌过程。 4. **优化发牌算法**:考虑特殊情况,如玩家数量变化或...

    随机数与洗牌算法

    这符合**费希尔-耶茨洗牌算法**(Fisher-Yates Shuffle),它是一种原地洗牌的方法,效率更高。 **费希尔-耶茨洗牌算法详解**: 1. **算法原理**:对于长度为n的数组,对每个位置i(从0到n-1),从当前位置到末尾...

    洗牌算法(感觉有点用)

    在计算机科学领域,洗牌算法是一种常见的随机化算法,主要用于将一个序列中的元素打乱顺序,使其呈现出随机分布的状态。这种算法在多种场景下都有广泛的应用,如游戏开发、密码学、数据处理等。本文将详细解析一种...

    随机生成牌和洗牌问题

    这是一种常见的洗牌算法,能够高效地对数组进行随机排序。算法的核心思想是从数组尾部开始,每次随机选择一个元素与当前位置的元素交换,从而保证每个元素被选中的概率相同。 **具体步骤:** - 初始化一个包含所有...

    洗牌算法思路讲解(程序员面试题)

    洗牌算法是编程领域中一个有趣的议题,常用于模拟各种随机事件,比如电子游戏中抽取卡片、抽奖系统等。本文将探讨三种不同的洗牌算法思路,它们各有优缺点,适用于不同的场景。 首先,我们来理解洗牌算法的核心目标...

    VB洗牌源代码 游戏算法示例

    首先,洗牌算法是编程中用于模拟洗牌过程的一种方法,确保每次执行都能产生不同的牌序,给玩家带来随机性和公平性。在VB中,我们可以使用各种方法来实现这一目标,但最常见的可能是Fisher-Yates(也称为Knuth)洗牌...

    随机洗牌程序 C源代码

    在编程领域,随机洗牌是一种常见的操作,常用于模拟游戏、算法测试或数据处理等场景。本篇将详细解析一个基于C语言实现的随机洗牌程序。首先,我们需要理解C语言的基本语法和随机数生成机制。 C语言是计算机科学中...

    完美洗牌问题线性算法的论文.rar

    通常,解决完美洗牌问题需要设计一种高效的算法,以确保所有可能的排列都被均匀地覆盖。这篇论文可能深入讨论了这个问题的起源,以及早期的解决方案和它们的局限性。 "yang2013.pdf"论文则可能关注“标准反等差映射...

    Baraja演示15种不同的洗牌特效

    3. **Fisher-Yates洗牌算法**:这是一种经典算法,其基本步骤包括从最后一个元素开始,每次选择一个随机索引并交换当前元素和随机索引对应的元素,直到遍历到第一个元素。这种算法保证了所有排列的概率相等。 4. **...

    基于折叠技术的大数据样本洗牌算法研究.pdf

    实验结果表明,在样本分段数和循环次数设定为样本总数的一定比例时,即分段数为5%,循环次数为2%,该算法相较于其他基于随机技术的洗牌算法,在时间效率、离散度和均匀度方面均表现出显著的优势。 这种基于折叠技术...

    猜数游戏-----洗牌算法的典型应用

    而在编程世界里,猜数游戏的实现往往离不开一种重要的算法——洗牌算法。洗牌算法,顾名思义,是模拟实际生活中洗扑克牌的过程,其目的是在随机顺序中排列一组数字或对象,从而增加游戏的不确定性和趣味性。本文将...

    python洗牌算法.md

    洗牌算法(Shuffle Algorithm)是一种常见的算法,主要用于随机地重新排列一组数据的顺序。在实际应用中,它经常被用于游戏开发、模拟实验以及各种需要随机化处理的场景。 #### 二、核心思想 洗牌算法的核心思想是...

    C经典算法之洗扑克牌(乱数排列)

    具体地,使用了经典的洗牌算法——Fisher-Yates洗牌算法的一个变体。这种算法的工作原理是从数组中随机选择一个元素,并与当前位置的元素交换,这样可以确保每张牌被选中的概率相等。 **3. 算法设计:洗牌算法** ...

    离散数学不完美的完美洗牌法scujcc期末作业,内含算法

    不完美的完美洗牌法虽然提供了一种理论上的洗牌策略,但它存在不完全随机性的问题,长期使用可能会导致某些模式的出现。优点在于其简洁的数学表达和易于实现,但缺点则在于其可能的可预测性。为了提高随机性,可以...

    javascript随机之洗牌算法深入分析

    在实际应用中,通常选用Fisher-Yates(又称Knuth)洗牌算法,它是一种更高效且保证均匀分布的方法。Fisher-Yates算法从数组的最后一个元素开始,随机选择一个位置与当前位置交换,直到遍历到第一个元素。其...

    Java实现模拟洗牌的程序

    2. 洗牌算法:这是程序的重点。Java中的洗牌通常通过 Fisher-Yates(也称为 Knuth)洗牌算法 实现。该算法通过遍历数组并随机交换当前元素与未遍历元素之一的位置来达到打乱顺序的目的。`java.util.Random`类可以...

    扑克牌洗牌程序

    洗牌程序的核心在于算法,它要求随机地重新排列一副扑克牌的顺序。在计算机科学中,这通常通过随机数生成器实现。在C#中,可以使用`System.Random`类来生成随机数。洗牌算法需要确保每张牌被洗到任何位置的概率是...

    易语言源码易语言抽牌算法模块源码

    2. 随机化算法:抽牌的核心在于随机化,需要确保每一次抽取的过程都是随机的,不能让玩家通过任何方式预测下一张牌会是什么。为了实现这一点,算法会调用随机数生成器来决定抽取的结果。 3. 抽取方式:在实际的抽牌...

    QtRandomNumber.rar

    洗牌算法是一种将一组数据(通常是一个数组或向量)随机重新排列的方法,其目的是使得原始顺序变得不可预测。在C++中,我们可以使用标准库中的`<algorithm>`头文件提供的`std::shuffle`函数来实现这一过程。该函数...

Global site tag (gtag.js) - Google Analytics