77

就像背景一样,我知道Fisher-Yates完美洗牌。这是一个很好的洗牌,它的 O(n) 复杂性和保证的一致性,如果不使用它我会很傻......在允许就地更新数组的环境中(所以在大多数情况下,如果不是全部,命令式编程环境)。

遗憾的是,函数式编程世界并没有让您访问可变状态。

然而,由于 Fisher-Yates,我找不到很多关于如何设计洗牌算法的文献。少数几个完全解决这个问题的地方在说,实际上,“所以这里是Fisher-Yates,这是你需要知道的所有洗牌”。最后,我不得不提出自己的解决方案。

我想出的解决方案可以像这样对任何数据列表进行洗牌:

  • 如果列表为空,则返回空集。
  • 如果列表有单个项目,则返回该单个项目。
  • 如果列表非空,则使用随机数生成器对列表进行分区,并将算法递归地应用于每个分区,组合结果。

在 Erlang 代码中,它看起来像这样:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(如果这对你来说看起来像是一种疯狂的快速排序,那么基本上就是这样。)

所以这是我的问题:同样的情况使得寻找不是 Fisher-Yates 的洗牌算法变得困难,这使得寻找分析洗牌算法的工具同样困难。我可以找到很多关于分析 PRNG 的均匀性、周期性等方面的文献,但没有很多关于如何分析 shuffle 的信息。(事实上​​,我在分析 shuffle 时发现的一些信息完全是错误的——很容易通过简单的技术被欺骗。)

所以我的问题是:我如何分析我的洗牌算法(假设random:uniform()调用那里的任务是生成具有良好特性的适当随机数)?我可以使用哪些数学工具来判断,例如,在 1..100 范围内的整数列表上运行 100,000 次洗牌器是否给了我合理的好洗牌结果?我自己做了一些测试(例如,比较随机播放中的增量和减量),但我想知道更多。

如果对洗牌算法本身有任何见解,那也将不胜感激。

4

4 回答 4

77

一般说明

我个人关于概率使用算法正确性的方法:如果你知道如何证明它是正确的,那么它可能是正确的;如果你不这样做,那肯定是错误的。

换句话说,尝试分析你能想出的每一种算法通常是没有希望的:你必须不断地寻找一种算法,直到你找到一个可以证明是正确的算法。

通过计算分布来分析随机算法

我知道一种“自动”分析洗牌(或更一般地说是随机使用算法)的方法,它比简单的“进行大量测试并检查一致性”更强。您可以机械地计算与算法的每个输入相关的分布。

总的想法是随机使用算法探索可能性世界的一部分。每次您的算法要求集合中的随机元素(掷硬币时{ true, } )时,您的算法有两种可能的结果,并且选择其中一种。false您可以更改您的算法,而不是返回可能的结果之一,而是并行探索所有解决方案并返回所有可能的结果以及相关的分布。

一般来说,这需要深入重写你的算法。如果您的语言支持定界延续,则不必这样做;您可以在要求随机元素的函数内部实现“探索所有可能的结果”(想法是随机生成器不是返回结果,而是捕获与您的程序关联的延续并以所有不同的结果运行它)。有关此方法的示例,请参阅 oleg 的HANSEI

一个中间的(可能不那么神秘的)解决方案是将这个“可能结果的世界”表示为一个单子,并使用诸如 Haskell 之类的具有单子编程设施的语言。这是您的算法变体¹的示例实现,在 Haskell 中,使用概率包的概率单子:

import Numeric.Probability.Distribution

shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
        (left, right) <- partition li
        sleft <- shuffleM left
        sright <- shuffleM right
        return (sleft ++ [pivot] ++ sright)
  where partition [] = return ([], [])
        partition (x:xs) = do
                  (left, right) <- partition xs
                  uniform [(x:left, right), (left, x:right)]

您可以针对给定的输入运行它,并获得输出分布:

*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
  [([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
   ([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]

你可以看到这个算法对于大小为 2 的输入是一致的,但在大小为 3 的输入上是不一致的。

与基于测试的方法的不同之处在于,我们可以在有限数量的步骤中获得绝对确定性:它可能非常大,因为它相当于对可能世界的详尽探索(但通常小于 2^N,如有类似结果的因式分解),但如果它返回非均匀分布,我们肯定知道该算法是错误的。当然,如果它返回 和 的均匀分布[1..N]1 <= N <= 100你只知道你的算法在大小为 100 的列表中是均匀的;它可能仍然是错误的。

¹:由于特定的枢轴处理,此算法是您的 Erlang 实现的变体。如果我不使用枢轴,就像您的情况一样,输入大小不再在每一步减小:该算法还考虑了所有输入都在左列表(或右列表)中并在无限循环中丢失的情况. 这是概率单子实现的一个弱点(如果一个算法的非终止概率为 0,分布计算可能仍然发散),我还不知道如何解决。

基于排序的洗牌

这是一个简单的算法,我相信我可以证明它是正确的:

  1. 为集合中的每个元素选择一个随机键。
  2. 如果键不是全部不同,请从步骤 1 重新开始。
  3. 按这些随机键对集合进行排序。

如果您知道发生碰撞的概率(两个随机数相等)足够低,则可以省略步骤 2,但没有它,洗牌不会完全一致。

如果您在 [1..N] 中选择您的钥匙,其中 N 是您收藏的长度,您将遇到很多冲突(生日问题)。如果您将密钥选择为 32 位整数,则在实践中发生冲突的概率很低,但仍会受到生日问题的影响。

如果您使用无限(延迟评估)位串作为键,而不是有限长度键,则冲突概率变为 0,并且不再需要检查不同性。

这是 OCaml 中的 shuffle 实现,使用惰性实数作为无限位串:

type 'a stream = Cons of 'a * 'a stream lazy_t

let rec real_number () =
  Cons (Random.bool (), lazy (real_number ()))

let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
    compare_real a' b'

let shuffle list =
  List.map snd
    (List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
       (List.map (fun x -> real_number (), x) list))

还有其他方法可以“纯洗牌”。一个不错的是 apfelmus 的基于归并排序的解决方案

算法考虑:前面算法的复杂度取决于所有键不同的概率。如果将它们选为 32 位整数,则特定键与另一个键发生冲突的概率约为 40 亿分之一。按这些键排序是 O(n log n),假设选择一个随机数是 O(1)。

如果你无限位串,你永远不必重新开始挑选,但复杂性与“平均评估流的多少元素”有关。我猜想它平均为 O(log n)(因此总共仍为 O(n log n)),但没有证据。

...我认为你的算法有效

经过更多反思,我认为(如 douplep),您的实现是正确的。这是一个非正式的解释。

列表中的每个元素都经过多次random:uniform() < 0.5测试。对于一个元素,您可以将这些测试的结果列表关联为布尔值列表或 { 0, 1}。在算法开始时,您不知道与这些数字中的任何一个关联的列表。在第一次partition调用之后,您知道每个列表的第一个元素,等等。当您的算法返回时,测试列表是完全已知的,并且根据这些列表对元素进行排序(按字典顺序排序,或被视为实数的二进制表示)数)。

因此,您的算法等效于按无限位串键进行排序。对列表进行分区的操作,让人想起快速排序在枢轴元素上的分区,实际上是一种在位串中的给定位置将具有值0的元素与具有值的元素分开的方式1

排序是统一的,因为位串都是不同的。实际上,在深度n递归调用期间,实数等于第 - 位的两个元素位于分区的同一侧。该算法仅在分区产生的所有列表为空或单例时终止:所有元素已被至少一个测试分隔,因此具有一个不同的二进制十进制。shufflen

概率终止

关于您的算法(或我等效的基于排序的方法)的一个微妙点是终止条件是probabilistic。Fisher-Yates 总是在已知步数(数组中的元素数)后终止。使用您的算法,终止取决于随机数生成器的输出。

有可能的输出会使您的算法发散,而不是终止。例如,如果随机数生成器始终输出0,则每次partition调用都将返回不变的输入列表,在该列表上递归调用 shuffle :您将无限循环。

但是,如果您确信您的随机数生成器是公平的,这不是问题:它不会作弊并且总是返回独立的均匀分布的结果。random:uniform() < 0.5在这种情况下,测试总是返回true(or )的概率false正好是 0 :

  • 前 N 个调用返回的概率true是 2^{-N}
  • 所有调用返回true的概率是前 N 个调用返回的事件对于所有 N 的无限交集的概率0;它是 2^{-N} 的下确界¹,即 0

¹:有关数学细节,请参阅http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

更一般地说,当且仅当某些元素与相同的布尔流相关联时,该算法才终止。这意味着至少两个元素具有相同的布尔流。但是两个随机布尔流相等的概率又是0:位置K的数字相等的概率是1/2,所以前N个数字相等的概率是2^{-N},同样分析适用。

因此,您知道您的算法以概率 1 终止。这是一个稍弱的保证,Fisher-Yates 算法总是终止。特别是,您很容易受到控制您的随机数生成器的邪恶对手的攻击。

使用更多概率论,您还可以计算给定输入长度下算法的运行时间分布。这超出了我的技术能力,但我认为这很好:我想您只需要平均查看 O(log N) 个前数字即可检查所有 N 个惰性流是否不同,以及运行时间更高的概率成倍下降。

于 2010-10-17T10:22:58.793 回答
23

如 Wikipedia 文章中所述,您的算法是基于排序的 shuffle。

一般来说,基于排序的 shuffle 的计算复杂度与底层排序算法相同(例如 O( n log n ) 平均值,基于快速排序的 shuffle 的最坏情况为O( n ²)),而分布不是完全一致,对于大多数实际目的,它应该足够接近一致。

Oleg Kiselyov 提供以下文章/讨论:

它更详细地介绍了基于排序的 shuffle 的局限性,并且还提供了 Fischer-Yates 策略的两种改编:一种朴素的 O( )一种,一种基于二叉树的 O( nlogn )一种。

遗憾的是,函数式编程世界并没有让您访问可变状态。

这不是真的:虽然纯函数式编程避免了副作用,但它支持访问具有一流效果的可变状态,而不需要副作用。

在这种情况下,您可以使用 Haskell 的可变数组来实现变异 Fischer–Yates 算法,如本教程中所述:

附录

随机排序的具体基础实际上是无限键基数排序:正如加什指出的那样,每个分区对应一个数字分组。

这样做的主要缺点与任何其他无限键排序 shuffle 相同:没有终止保证。尽管随着比较的进行终止的可能性增加,但从来没有上限:最坏情况的复杂度是 O(∞)。

于 2010-10-15T19:31:36.530 回答
3

前段时间我在做一些类似的事情,特别是你可能对 Clojure 的向量感兴趣,它们是功能性的和不可变的,但仍然具有 O(1) 随机访问/更新特性。这两个要点有几个实现“从这个 M 大小的列表中随机取 N 个元素”;如果您让 N=M,其中至少一个会变成 Fisher-Yates 的功能实现。

https://gist.github.com/805546

https://gist.github.com/805747

于 2011-03-08T20:46:21.143 回答
1

基于How to test randomness (case in point - Shuffle),我建议:

随机播放(中等大小)由相等数量的 0 和 1 组成的数组。重复并连接直到无聊。使用这些作为顽固测试的输入。如果你有一个很好的洗牌,那么你应该生成零和一的随机序列(需要注意的是,在中型数组的边界处,零(或一)的累积过量为零,你希望测试检测到,但“中”越大,他们这样做的可能性就越小)。

请注意,测试可能会出于以下三个原因拒绝您的随机播放:

  • 洗牌算法不好,
  • 洗牌器或初始化期间使用的随机数生成器坏了,或者
  • 测试实施很糟糕。

如果任何测试被拒绝,您将必须解决这种情况。

顽固测试的各种改编(为了解决某些数字,我使用了顽固页面的源代码)。自适应的原理机制是让shuffle算法作为一个均匀分布的随机比特的来源。

  • 生日间距:在n 个零的数组中,插入 log n个。随机播放。重复直到无聊。构造间距分布,与指数分布进行比较。你应该用不同的初始化策略来执行这个实验——前面的,最后的,中间的一起,随机分散的。(后者具有最大的风险,即初始化随机化不良(相对于改组随机化)导致拒绝改组。)这实际上可以用相同值的块来完成,但问题是它在分布中引入了相关性(一和二不能在一次洗牌中位于同一位置)。
  • 重叠排列:多次洗牌五个值。验证这 120 个结果的可能性是否相同。(卡方检验,119 个自由度——顽固检验 (cdoperm5.c) 使用 99 个自由度,但这(主要)是由使用输入序列的重叠子序列引起的序列相关性的产物。)
  • 矩阵的秩:从 2*(6*8)^2 = 4608 位从 shuffle 相等数量的 0 和 1 中选择 6 个不重叠的 8 位子串。将这些视为 6×8 二进制矩阵并计算其秩。重复 100,000 个矩阵。(将 0-4 的等级汇集在一起​​。然后等级是 6、5 或 0-4。)等级的预期分数是 0.773118、0.217439、0.009443。卡方与具有两个自由度的观察分数进行比较。31×31 和 32×32 测试是相似的。分别汇集 0-28 和 0-29 的等级。预期分数为 0.2887880952、0.5775761902、0.1283502644、0.0052854502。卡方检验具有三个自由度。

等等...

您可能还希望利用dieharder和/或ent来进行类似的适应性测试。

于 2015-07-30T00:58:11.860 回答