什么，如果有的话，这个洗牌algorithm是错误的，我怎么知道？
就像背景一样，我知道Fisher-Yates完美的洗牌。 O（n）的复杂性和保证的一致性是一个很好的洗牌，我不会使用它…在允许数组就地更新的环境中（所以在大多数情况下，即使不是全部， 命令式编程环境）。
可悲的是function性编程世界并不能让你进入可变状态。
然而，由于Fisher-Yates，关于如何devise一个洗牌algorithm，并没有太多的文献可以find。 事实上，几乎没有一个地方可以这样说，“所以这里就是你需要知道的所有洗牌的费希尔 – 耶茨。 最后，我必须拿出我自己的解决scheme。
我想出了这样的解决scheme来洗牌任何数据列表：
- 如果列表为空，则返回空集。
- 如果列表中有单个项目，则返回该单个项目。
- 如果列表不是空的，则用随机数生成器对列表进行分区，并recursion地将algorithm应用于每个分区，然后组装结果。
在Erlang代码中，它看起来像这样：
shuffle([]) -> []; shuffle([L]) -> [L]; shuffle(L) -> {Left, Right} = lists:partition(fun(_) -> random:uniform() < 0.5 end, L), shuffle(Left) ++ shuffle(Right). （如果这看起来像一个疯狂的快速sorting，那么基本上就是这样。）
所以这就是我的问题：寻找不是Fisher-Yates的混洗algorithm的相同情况使得寻找工具来分析洗牌algorithm同样困难。 在分析PRNG的一致性，周期性等方面，我可以find许多文献，但是关于如何分析洗牌的信息却并不多。 （事实上，我在分析洗牌时发现的一些信息显然是错误的 – 很容易通过简单的技术欺骗。）
所以我的问题是：我如何分析我的洗牌algorithm（假设random:uniform()调用那里有产生具有良好特性的适当随机数的任务）？ 我可以用什么math工具来判断，在1..100的整数列表中，是否有100,000次洗牌机运行给了我合理的洗牌结果？ 我已经做了一些我自己的testing（例如比较增量在shuffles中的递减），但我想知道更多。
如果有什么洞察到洗牌algorithm本身，也将不胜感激。
一般的评论
我个人关于概率使用algorithm的正确性的方法是：如果你知道如何certificate它是正确的，那么它可能是正确的; 如果你不这样做，那肯定是错的。
换句话说，试图分析每个可能出现的algorithm通常是绝望的：你必须继续寻找一个algorithm，直到find一个可以certificate正确的algorithm。
通过计算分布来分析随机algorithm
我知道有一种方法可以“自动”分析洗牌（或更一般的随机使用algorithm），这比简单的“扔大量的testing并检查一致性”更强。 您可以机械地计算与algorithm的每个input相关的分布。
总体思路是随机使用algorithm探索可能性世界的一部分。 每次你的algorithm要求在一个集合中有一个随机元素（{ true ， false }）时，你的algorithm有两种可能的结果，其中一个被选中。 您可以更改algorithm，使其不是返回可能的结果之一，而是并行探索所有解决scheme，并返回所有可能的结果以及相关的分布。
一般来说，这需要重写你的algorithm。 如果你的语言支持分隔的延续，你不需要; 你可以在函数内部实现“探索所有可能的结果”，然后寻找一个随机元素（这个想法是随机生成器，而不是返回一个结果，捕获与你的程序相关的延续并运行所有不同的结果）。 有关此方法的示例，请参阅oleg的HANSEI 。
一个中介，可能不那么神秘的解决scheme就是将这个“可能结果的世界”当作一个monad来表示，并且使用像Haskell这样的语言来提供一元编程的function。 下面是一个在Haskell中使用概率包的概率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)]
你可以运行一个给定的input，并得到输出分布：
*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)]
您可以看到，该algorithm在input大小为2的情况下是均匀的，但在大小为3的input上是不均匀的。
与基于testing的方法的区别在于，我们可以在有限的步骤中获得绝对的确定性：它可以是相当大的，因为它等于对可能世界的详尽探索（但是通常小于2 ^ N，如有相似结果的因素），但如果它返回一个不均匀的分布，我们肯定知道algorithm是错误的。 当然，如果返回[1..N]和1 <= N <= 100的均匀分布，那么只知道你的algorithm是一致的，直到大小为100的列表; 它可能仍然是错误的。
¹：由于特定的数据透视处理，这个algorithm是Erlang实现的变体。 如果我不使用pivot，就像你的情况一样，input大小在每一步都不会减less：algorithm也考虑所有input都在左边列表（或右边列表）的情况，并且在无限循环中迷路。 这是monad实现概率的一个弱点（如果一个algorithm有一个非终结概率0，分布计算可能仍然会发散），我还不知道如何解决。
基于sorting的洗牌
这是一个简单的algorithm，我觉得我可以certificate是正确的：
- 为您的集合中的每个元素select一个随机密钥。
- 如果密钥不完全相同，则从步骤1重新开始。
- 通过这些随机密钥对收集进行sorting。
如果知道碰撞概率（两个随机数相等）足够低，则可以省略步骤2，但如果没有，则洗牌不是完全一致的。
如果您在[1..N]中select您的密钥，其中N是您collections的长度，则会有很多碰撞（ 生日问题 ）。 如果你把你的密钥作为一个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 ab = 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的解决scheme 。
algorithm考虑：以前algorithm的复杂性取决于所有密钥不同的概率。 如果你select它们作为32位整数，那么你就有40亿分之一的概率使一个特定的键与另一个键相冲突。 按这些键sorting是O（n log n），假设select一个随机数是O（1）。
如果你有无限的比特串，你就不必重新启动select，但是复杂度与“平均评估多less个stream元素”有关。 我猜想平均为O（log n）（因此总共为O（n log n）），但是没有证据。
…我认为你的algorithm的作品
经过更多的反思，我想（像douplep），你的实现是正确的。 这是一个非正式的解释。
您的列表中的每个元素都会被几个random:uniform() < 0.5 testing random:uniform() < 0.5testing。 对于元素，您可以将这些testing的结果列表关联起来，作为布尔值列表或{ 0 }。 在algorithm的开始，你不知道与这些数字相关的列表。 在第一次partition调用之后，你知道每个列表的第一个元素，等等。当你的algorithm返回时，testing列表是完全已知的，元素根据这些列表sorting（按字典顺序sorting，或者被认为是二进制表示实数）。
所以，你的algorithm等价于无限位string键sorting。 分割列表的行为，让人联想到快速sorting在主元素上的划分，实际上是对位列中的给定位置分离具有评估1的元素具有评估0的元素的一种方式。
sorting是一致的，因为比特串是完全不同的。 实际上，具有等于第n个比特的实数的两个元素位于在深度n的recursionshuffle调用期间发生的分区的同一侧。 algorithm只有在所有由分区产生的列表为空或单例时才会终止：所有元素都被至less一个testing分开，因此有一个不同的二进制小数。
概率终止
关于你的algorithm（或者我的等价的基于sorting的方法）的一个微妙之处是终止条件是概率的 。 Fisher-Yates总是在已知的步数（数组中元素的数量）之后终止。 用你的algorithm，终止依赖于随机数发生器的输出。
有可能的输出会使你的algorithm发散 ，而不是终止。 例如，如果随机数发生器总是输出0 ，则每个partition调用将不变地返回input列表，您在其上recursion调用shuffle：将无限循环。
但是，如果您确信您的随机数生成器是公平的，那么这不是问题：它不会作弊并始终返回独立的均匀分布结果。 在这种情况下，testingrandom:uniform() < 0.5始终返回true （或false ）的概率恰好为0：
- 前N个调用返回为
true概率是2 ^ { – N} - 所有调用返回
true的概率是N个调用返回0的事件的所有N的无限交集的概率; 它是2 ^ { – N}的下限¹，即0
¹：有关math细节，请参阅http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets
更一般地说，当且仅当某些元素关联到相同的布尔stream时，algorithm才会终止。 这意味着至less有两个元素具有相同的布尔stream。 但是两个随机布尔stream相等的概率又是0：位置K处的数字相等的概率是1/2，所以N个第一个数字相等的概率是2 ^ { – N}，并且相同分析适用。
因此，您知道您的algorithm以概率1结束 。 Fisher-Yatesalgorithm总是终止的 ，这是一个稍弱的保证。 特别是，你很容易受到控制你的随机数发生器的邪恶对手的攻击。
利用更多的概率理论，您还可以计算给定input长度的algorithm的运行时间分布。 这超出了我的技术能力，但我认为它是好的：我想你只需要平均看O（log N）的第一个数字来检查所有N个懒惰stream是不同的，并且运行时间要高得多成指数下降
您的algorithm是基于sorting的洗牌，如维基百科文章中所讨论的。
一般来说，基于sorting的混洗的计算复杂性与基本的sortingalgorithm相同（例如，基于快速sorting的混洗的最坏情况为O（ n log n ）平均值，O（ n 2）），而分布不是完全一致，它应该接近足够接近足够的最实际的目的。
奥列格Kiselyov提供以下文章/讨论：
- 可以完美的随机洗牌和纯粹的function实现
它涵盖了基于sorting的混洗的局限性，并且还提供了对Fischer-Yates策略的两个改进：一个天真的O（n²）和一个基于二叉树的O（ n log n ）。
可悲的是function性编程世界并不能让你进入可变状态。
这是不正确的：虽然纯函数式编程避免了副作用 ，但它支持访问具有一stream效果的可变状态，而不需要副作用。
在这种情况下，您可以使用Haskell的可变数组来实现本教程中描述的变异Fischer-Yatesalgorithm：
- 哈斯克尔洗牌 （布雷特霍尔）
附录
你的随机sorting的具体基础实际上是一个无限的基数sorting ：正如gasche指出的，每个分区对应一个数字分组。
这样做的主要缺点与其他无限分类洗牌相同：没有终止保证。 虽然终止的可能性随着比较的进行而增加，但是从来没有上限：最坏的情况是O（∞）。
我刚刚在做一些与此类似的事情，特别是你可能对Clojure的向量感兴趣，这些向量是function性和不可变的，但是仍然具有O（1）随机访问/更新特性。 这两个要点有几个“从这个M大小的列表中随机取N个元素”的实现。 如果你让N = M，至less有一个变成了Fisher-Yates的function实现。
基于如何testing随机性（例如Shuffling） ，我build议：
随机（中等大小）数组由相等数量的零和一组成。 重复和连接，直到无聊。 使用这些作为顽固testing的input。 如果你有一个很好的洗牌，那么你应该产生零和一个随机序列（与在中等大小的arrays的边界累积超过零（或一个）为零），你希望testing检测，但更大的“中等”是这样做的可能性较小）。
请注意，testing可以拒绝您的洗牌，原因有三：
- 洗牌algorithm不好，
- 洗牌机使用的随机数发生器或初始化过程中的随机数发生器是不好的，或者
- testing实施不好。
如果有任何testing拒绝，您将不得不解决这种情况。
顽固的testing的各种各样的适应（解决一些数字，我使用了来自死硬的页的来源 ）。 适应的主要机制是使混洗algorithm成为均匀分布的随机比特的来源。
- 生日间隔：在n个零的数组中，插入loggingn个。 洗牌。 重复，直到无聊。 构build一对一距离的分布，与指数分布进行比较。 你应该用不同的初始化策略来执行这个实验 – 前面的那些，最后的那些，中间的一起，随机散布的那些。 （后者具有最坏的初始化随机化（就混洗随机化而言）产生对混洗的拒绝的危险。）这实际上可以用相同值的块来完成，但是具有在分布中引入相关性的问题（一个和两个不能在一个洗牌中的相同位置）。
- 重叠置换：一堆次洗牌五个值。 确认120个结果大致相同的可能性。 （卡方检验，119自由度 – 顽固testing（cdoperm5.c）使用99个自由度，但这（大部分）是由使用input序列的重叠子序列引起的序列相关性的人造物。
- matrix排列：从2 *（6 * 8）^ 2 = 4608位混洗相等数量的零和1，select6个不重叠的8位子串。 将这些视为一个6×8的二进制matrix并计算其秩。 重复100,000个matrix。 （合计0-4等级，等级分别为6,5或0-4）预计的等级分数为0.773118,0.217439,0.009443。 卡方与观察到的具有两个自由度的分数进行比较。 31乘31和32乘32的testing是相似的。 0-28和0-29分别汇集在一起。 预期的分数是0.2887880952,0.5775761902,0.1383502644,0.005254502。 卡方检验有三个自由度。
等等…
您也可能希望利用迪恩和/或进行类似的适应性testing。
