algorithm - 这个改组算法有什么问题，我怎么知道？

Question

作为背景，我知道 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 的信息并不多。 (确实，我在分析洗牌时发现的一些信息完全是错误的——很容易被简单的技术欺骗。)

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

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

Answer 1

一般备注

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

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

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

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

总体思路是随机使用算法探索可能性世界的一部分。每次您的算法在抛硬币时要求一组随机元素({ true , false })时，您的算法有两种可能的结果，其中一个被选中。您可以更改您的算法，以便它不是返回一种可能的结果，而是并行探索所有解决方案并返回所有可能的结果以及相关的分布。

通常，这需要深入重写您的算法。如果您的语言支持分隔的延续，则不必；您可以在要求随机元素的函数中实现“探索所有可能的结果”(这个想法是随机生成器，而不是返回结果，捕获与您的程序相关联的延续并以所有不同的结果运行它)。有关此方法的示例，请参阅 oleg 的 HANSEI 。

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

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 实现的变体。如果我不使用枢轴，就像你的情况一样，输入大小不再在每一步减少:算法还考虑所有输入都在左列表(或右列表)中的情况，并在无限循环中迷失.这是概率 monad 实现的一个弱点(如果一个算法的非终止概率为 0，分布计算可能仍然发散)，我还不知道如何解决。

基于排序的洗牌

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

为集合中的每个元素选择一个随机键。

如果key不完全不同，从步骤1重新开始。

按这些随机键对集合进行排序。

如果您知道碰撞的概率(选取的两个随机数相等)足够低，则可以省略第 2 步，但没有它，洗牌就不是完全均匀的。

如果你在 [1..N] 中选择你的键，其中 N 是你的集合的长度，你会遇到很多冲突( Birthday problem )。如果您将 key 选择为 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 的 mergesort-based solution 。

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

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

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

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

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

所以，你的算法相当于按无限位串键排序。对列表进行分区的操作，让人想起快速排序对主元元素的分区，实际上是一种将位串中给定位置的值为 0x2518122231343141 的元素与值为 0 的元素分开的方法。

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

概率终止

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

有可能的输出会使您的算法发散，而不是终止。例如，如果随机数生成器始终输出 n ，则每个 0 调用将返回未更改的输入列表，您将在其上递归调用 shuffle :您将无限循环。

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

前N次调用返回false的概率为2^{-N}

所有调用返回 true 的概率是前 N 个调用返回 true 的事件的所有 N 个无限交集的概率；它是 2^{-N} 的下限¹，即 0

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

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

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

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