Java教程

洗牌算法

本文主要是介绍洗牌算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

一、什么是洗牌算法

二、如何去打乱

三、例题


一、什么是洗牌算法

现在有一副扑克牌,让你去洗牌,怎么洗牌才能让每一种牌之间的组合出现的概率相等?

简单的问题往往隐藏了重要信息,比如这里我们可以将洗牌理解为将这副牌打乱,那么什么才叫乱呢?

其中有两个要素:

  • 随机的结果要能够覆盖所有的情况,(譬如 n张牌,最后的结果有 n! 情况,结果所有顺序必须都能够出现)。
  • 所有出现的结果 概率 相等。

二、如何去打乱

首先,设定我们已经拥有了系统提供的rand函数,能够提供一个给定范围内的随机数,而且我们假定这个随机过程满足给定范围内的均匀分布。

以洗牌为例:

我们洗牌的细粒度最小的动作,应该是两张牌对换。(两堆对换,一张牌抽出放在顶部等动作都是O(n)的复杂度)

要达到打乱的效果,我们比较容易想到的方式是 n张牌组成的全新牌堆:

  • 洗1次,会得到n种可能的结果;
  • 洗2次,会得到n*(n-1)种结果(减一是因为当第一次和第二次为互逆过程,等于回到最开始,没有新的排列出现)
  • 洗3次,会得到n*(n-1)*(n-2)种结果;
  • ... ...
  • 洗n次,会得到n!种结果,此时,已经完全充满n!的空间,洗更多次,样本空间不扩充。

所以,到这里,可以知道,对于一副牌,最少只要随机的交换n次,才能在概率的意义上,让洗牌达到足够的“乱”,那么现在问题来了,如何选择一个好的算法?

一个比较容易想到的,简单粗暴的方法是,按照上面的文字,写出这样的伪代码:

    for(int i=0;i<suit.length;i++)
    {
        random1 = Random.next(1,n);
        random2 = Random.next(1,n);
        exchange(suit[random1],suit[random2]);
    }

上面的算法在设计上能够充满整个样本空间,确实存在n!种可能性,但是不够好。

为什么不够好呢,因为这种算法不能够 确保 照顾到每一张牌。

随机洗牌的随机在于其不确定性,对于n张牌组成的有序排列,经过了n次随机选择,漏掉1只牌从未选过的概率不为0,而且,随着牌的张数数量增加,这个概率非常可观。

现在就是经典的Fisher–Yates算法登场的时候了。下面给出伪代码:

    for(int i=suit.length-1;i>0;i--)
    {
        random1 = Random.next(1,i);
        exchange(suit[random1],suit[i]);
    }

这个算法和之前的算法最大的不同在于,每一次抽卡的范围在慢慢变小,具体的步骤可以看wiki给出的例子,我就直接照搬过来:

图标

img

img

img

img

这个算法在样本空间上,跟前面简单粗暴的随机抽取一样。

充满了n!的样本空间,好在哪里呢?

因为它利用了抽卡本身的顺序,【保证照顾】到了每一张原本序列中的卡,

而简单粗暴随机抽取存在出现重复位置的可能性,就等于浪费了一次排序的机会,

换句话说,其等效抽卡次数因为出现了过去相同的洗法,有效洗牌次数下降,样本空间缩小,无法充满整个n!空间,所以有效性会下降。

而Fisher–Yates算法在原理上保证了不会出现浪费次数,重复选择的情况,导致样本空间一直保持n!,没有坍缩,这就是其在数学意义上优秀的原因。

三、例题

给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

  • Solution(int[] nums) 使用整数数组 nums 初始化对象
  • int[] reset() 重设数组到它的初始状态并返回
  • int[] shuffle() 返回数组随机打乱后的结果

Demo 

 

这篇关于洗牌算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!