如果有什么问题的话,这个洗牌算法有什么问题,我怎么知道呢?

总评论

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

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

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

我知道有一种方法可以“自动”分析一个比简单的“抛出大量测试并检查一致性”更强大的混乱(或者更普遍地说是一个随机使用的算法)。您可以机械地计算与算法的每个输入相关联的分布。

一般的想法是,随机使用的算法探索一个可能世界的一部分。每次您的算法在集合中请求随机元素时({ true , false }翻转硬币时),您的算法有两种可能的结果,其中一种是选中的。你可以改变你的算法,这样,它就不会返回一个可能的结果,而是探索 全部的 并行解决方案,并返回所有可能的结果和相关的分布。

一般来说,这需要对算法进行深度重写。如果您的语言支持带分隔符的延续,则不必这样做;您可以在请求随机元素的函数内部实现“对所有可能结果的探索”(其思想是,随机生成器不返回结果,而是捕获与程序相关联的延续,并使用所有不同的结果运行它)。有关此方法的示例,请参见Oleg's HANSEI .

一个中介,可能不那么神秘,解决方案是将这个“可能结果的世界”表示为一个monad,并使用诸如haskell这样的语言以及用于一个monadic编程的工具。下面是在Haskell中使用 probability 包裹:

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实现的变体。如果我不使用Pivot,就像在您的例子中一样,输入的大小在每一步都不会减少:算法还考虑了所有输入都在左列表(或右列表)中的情况,并在无限循环中丢失。这是概率monad实现的一个弱点(如果一个算法的概率为0,则分布计算可能仍然存在分歧),我还不知道如何解决。

基于排序的无序播放

下面是一个简单的算法,我确信我可以证明是正确的:

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

如果您知道碰撞的概率(两个随机选取的数字相等)足够低,则可以省略步骤2,但没有它,无序移动就不完全均匀。

如果您在[1..n]中选择您的密钥,其中n是集合的长度,则会发生很多冲突。( Birthday problem )如果您将密钥选为32位整数,在实践中冲突的可能性很低,但仍会受到生日问题的影响。

如果使用无限(延迟计算)位串作为键,而不是有限长度的键,则冲突的概率将变为0,并且不再需要检查是否清晰。

以下是OCAML中的无序处理实现,使用懒惰实数作为无限位串:

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))

还有其他方法可以“纯粹的洗牌”。一个好的是阿普非默斯的 mergesort-based solution .

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

如果是无限位串,则不必重新开始选取,但复杂度与“平均计算流中有多少个元素”有关。我推测它是O(log n)的平均值(因此仍然是O(n log n),但没有证据。

…我认为你的算法有效

在更多的反射之后,我认为(像douplep),您的实现是正确的。这是一个非正式的解释。

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

因此,您的算法相当于使用无限位串键进行排序。对列表进行分区的操作,类似于QuickSort对Pivot元素的分区,实际上是一种将具有值的元素(对于位串中的给定位置)进行分隔的方法。 零 从有价值的要素 一 .

排序是统一的,因为位串都是不同的。实际上,实数等于 n -th位在递归期间发生的分区的同一侧 shuffle 深度呼唤 n . 只有当分区产生的所有列表都是空的或是单例时,算法才会终止:所有元素都被至少一个测试分隔开,因此具有一个不同的二进制小数。

概率终止

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

有可能的输出会使您的算法 偏离 ,不终止。例如,如果随机数生成器总是输出 零 ,每一个 分区 调用将返回未更改的输入列表,在该列表上递归调用shuffle:您将无限循环。

然而,如果你确信你的随机数生成器是公平的,这不是一个问题:它不会作弊,并且总是返回独立的均匀分布的结果。在这种情况下,测试 随机:uniform()<0.5 总是回报 真 (或) 假 )正好是0:

• 前n个调用返回的概率 真 是2 ^ {-n}
• 所有呼叫返回的概率 真 是前n个调用返回的事件的无穷交集的概率。 零 ;是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(logn)的第一位数字的平均值就可以检查所有n个惰性流是否都不同,并且更高运行时间的概率以指数形式减少。

正如维基百科文章中所讨论的,您的算法是基于排序的无序排列。

一般来说,基于排序的无序处理的计算复杂性与底层排序算法(例如O.( n 日志 n 平均值,O( n )最坏的情况是基于快速排序的随机播放),而分布不是 完美 统一,它应该接近统一足够接近最实际的目的。

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

• Provably perfect random shuffling and its pure functional implementations

它更详细地说明了基于排序的无序处理的局限性,并提供了两种对费希尔战略的调整:一种是简单的( n )一种是基于二叉树的( n 日志 n 一)。

遗憾的是,函数式编程世界没有给你访问可变状态的权限。

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

在这种情况下,可以使用haskell的可变数组来实现本教程中描述的可变Fischeryates算法:

• Haskell Shuffling (Brett Hall)

补遗

洗牌排序的特定基础实际上是无限的密钥。 radix sort :正如Gasche指出的,每个分区对应一个数字分组。

其主要缺点与任何其他无限键排序混乱相同:没有终止保证。虽然终止的可能性随着比较的进行而增加,但从来没有上限:最坏情况下的复杂性是o()。

不久前我做了一些类似的事情,特别是你可能对Clojure的向量感兴趣,它是功能性的和不变的,但仍然具有O(1)随机访问/更新特性。这两个gist有“从这个m-sized列表中随机抽取n个元素”的几个实现;如果允许n=m,其中至少有一个会变成fisher-yates的函数实现。

https://gist.github.com/805546

https://gist.github.com/805747

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

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

请注意,测试可以拒绝洗牌有三个原因:

• 洗牌算法不好,
• 洗牌机或初始化过程中使用的随机数生成器损坏,或
• 测试实现不好。

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

不同的适应 diehard tests (为了解决某些数字,我使用 source 从 diehard page )自适应的主要机制是使随机位随机乱序算法成为均匀分布的随机位源。

• 生日间隔:以数组形式 n 零,插入日志 n 那些。洗牌。重复直到无聊。构造一个距离之间的分布,与指数分布进行比较。您应该使用不同的初始化策略来执行这个实验——前面的策略,后面的策略,中间的策略,随机分散的策略。(后者具有最大的风险,即不好的初始化随机化(关于洗牌随机化)会导致洗牌被拒绝。)这实际上可以用相同值的块来实现,但存在这样一个问题:它在分布中引入了相关性(一个和两个不能在一个单独的位置上处于相同的位置)洗牌)
• 重叠排列:将五个值随机排列一次。验证120个结果的可能性大致相同。(卡方检验,119自由度——迪哈德检验(cdoperm5.c)使用99自由度,但这(大部分)是由于使用输入序列的重叠子序列而导致的序列相关性伪影。)
• 矩阵的秩:从2*(6*8)^2=4608位(从0和1的等号洗牌中),选择6个不重叠的8位子串。把它们看作一个6乘8的二元矩阵并计算它的秩。重复10万个矩阵。(共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 进行类似的适应性测试。