新的方案是从牌套里随机找到两个位置,将其位置的牌交换。重复若干次后,便可以将牌洗乱。这里最关键的是需要找到一个合适的重复次数。
这个问题首先需要定义什么叫作“洗乱”。
我随便给出了一个定义:在洗牌过程中,任意一张牌不被抽到交换的概率小于 1/1000 。(这个定义不太符合直观感觉,这个下面会讨论)
简单的列出方程:( (n-2)/n ) ^ m <=1/1000 得到 m >= -3* ln 10 / ln (1-2/n)
对于 52 张牌,大约是 176 次。
之后,另一个同事给了我另一个方案。产生 N 个不易发生碰撞的随机数,比如 (0,1) 的浮点数,或是 [0,4G) 的整数。将这些数字排序,则可以得到一个被打乱次序的序列。
这个方案看起来更好,因为更接近洗乱牌的目的。我重新给一个“洗乱”的定义:每张牌在每个位置出现的概率相同。
反过来,我想知道前面我给出的交换法洗牌有多接近它。
要得到严格的数学分析似乎很困难。偷懒 google 了一下,原来好多人研究过类似问题了。看这里:
http://mathworld.wolfram.com/Shuffle.html
从这个链接找过去,有一篇论文 。它讨论了另一种类似的洗牌方法,即第一次把第一张和随机一张牌交换,第二次把第二张和随机一张牌交换…… 重复做 N 次。
当 N 大于等于 18 时,用这个方法洗牌后,居然恒等排列(identity permutation)是最有可能出现的。(所谓恒等排列大概是指第 n 张排在第 n 个位置)。论文太长没精力读,不过这个结论还真是让人惊奇啊。
还有你自己实现的那个也不咋地, 最简单的
for(int i=0;i<n;i++){
swapArray(i, random(i,n))
}
算法导法里的一个算法:
function randomize(A)
n=A.length
for i=1 to n
j=random(i,n)
swap A[i],A[j]
分享到:
相关推荐
【洗牌算法】是计算机科学中用于生成等概率随机序列的一种方法,常见于各种需要随机化元素顺序的场景,如游戏、模拟等。洗牌算法的主要目标是确保原数组中的每个元素在打乱后都有相等的概率出现在序列的任何位置。 ...
### 洗牌算法解析与实现 在计算机科学领域,洗牌算法是一种常见的随机化算法,主要用于将一个序列中的元素打乱顺序,使其呈现出随机分布的状态。这种算法在多种场景下都有广泛的应用,如游戏开发、密码学、数据处理...
完美洗牌算法是一种高效地对一个包含两个子序列的数组进行交错排列的算法。这个问题源自于将一个数组从`{a1 a2 a3 ... an b1 b2 b3 ... bn}`重新排列成`{a1 b1 a2 b2 ... an bn}`,要求在O(n)的时间复杂度内完成,且...
洗牌算法是编程领域中一个有趣的议题,常用于模拟各种随机事件,比如电子游戏中抽取卡片、抽奖系统等。本文将探讨三种不同的洗牌算法思路,它们各有优缺点,适用于不同的场景。 首先,我们来理解洗牌算法的核心目标...
传统的洗牌算法往往基于随机技术,存在效率低下的问题,尤其是当样本量巨大时,对系统资源的需求量会大幅增加,导致时间效率低下。为了解决这一问题,文中提出了基于折叠技术的大数据样本洗牌算法。 折叠技术是一种...
### 随机数生成与洗牌算法 #### 一、随机数生成 **定义**:随机数是指在一定范围内,各个数值出现的概率相同且无法预测的数字。 **特性**: 1. **不可预测性**:任何算法都无法事先确定生成的具体数值。 2. **...
3. **优化洗牌算法**:虽然Collections.shuffle()已经足够随机,但也可以通过自定义随机数生成器或者Fisher-Yates(Knuth)洗牌算法来进一步理解洗牌过程。 4. **优化发牌算法**:考虑特殊情况,如玩家数量变化或...
《猜数游戏——洗牌算法的深度解析与应用》 猜数游戏,作为一种常见的娱乐活动,经常被用于增进朋友间的互动和智力挑战。而在编程世界里,猜数游戏的实现往往离不开一种重要的算法——洗牌算法。洗牌算法,顾名思义...
### 洗牌算法概述 #### 一、概念介绍 洗牌算法(Shuffle Algorithm)是一种常见的算法,主要用于随机地重新排列一组数据的顺序。在实际应用中,它经常被用于游戏开发、模拟实验以及各种需要随机化处理的场景。 ###...
VBS的洗牌算法 算法类资源 可以看看
在大数据处理领域,样本洗牌算法是一项至关重要的技术,它主要应用于数据预处理阶段,以确保数据集的随机性和无偏性。"基于折叠技术的大数据样本洗牌算法研究"这个主题聚焦于如何利用折叠技术优化大数据环境下的样本...
洗牌算法.md
具体地,使用了经典的洗牌算法——Fisher-Yates洗牌算法的一个变体。这种算法的工作原理是从数组中随机选择一个元素,并与当前位置的元素交换,这样可以确保每张牌被选中的概率相等。 **3. 算法设计:洗牌算法** ...
这里我们采用了一种名为Fisher-Yates(也称为Knuth)洗牌算法的方法,它是一种保证均匀随机性的洗牌算法。 首先,我们定义了一个变量`$card_num`,它代表我们要洗的牌的数量,例如一副扑克牌有54张。接着,我们调用...
功能介绍: 在一个规定的范围内生成指定数量不重复的随机数 理论基础: 基于基础的洗牌算法而设计出来的。当n无限接近于max时,即使max很大,时间复杂度能稳定在O(1)。
在IT领域,尤其是在游戏开发、模拟实验或者加密技术中,洗牌算法经常被用来实现随机化数据序列。本文将深入探讨“QtRandomNumber.rar”压缩包中的内容,它涉及到C++实现洗牌算法的知识点。 首先,让我们了解什么是...
Python源码-洗牌算法
java的21点牌类游戏-自带洗牌算法与机器AI---【课程设计】 https://blog.csdn.net/dearmite/article/details/132301832#comments_28170675 本系列校训 用免费公开视频,卷飞培训班哈人!打死不报班,赚钱靠狠干! ...