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

作为背景，我知道 Fisher-Yates的完美洗牌。它的 O (n)复杂性和保证的一致性是一个很好的混乱，如果不在允许就地更新数组的环境中使用它，我就是一个傻瓜(如果不是所有的话，那么在大多数 势在必行编程环境中也是如此)。

遗憾的是，函数式编程世界不允许您访问可变状态。

然而，由于 Fisher-Yates 的缘故，我找不到太多关于如何设计洗牌算法的文献。实际上，少数几个提到这个问题的地方，在说出“这就是费舍尔-耶茨，你需要知道的所有洗牌方法”之前，都做了简短的说明。最后，我不得不想出自己的解决办法。

我提出的解决方案就是这样对任何数据列表进行洗牌:

  • 如果列表为空，则返回空集。
  • 如果列表中只有一个项，则返回该项。
  • 如果列表不是空的，则使用随机数生成器对列表进行分区，并递归地将该算法应用于每个分区，组装结果。

在 Erlang 代码中，它看起来是这样的:

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

(如果这看起来像是一个疯狂的快速排序，那么，基本上就是这样。)

So here's my problem: the same situation that makes finding shuffling algorithms that aren't Fisher-Yates difficult makes finding tools to 分析 a shuffling algorithm equally difficult. There's lots of literature I can find on analysing PRNGs for uniformity, periodicity, etc. but not a lot of information out there on how to analyse a shuffle. (Indeed some of the information I found on analysing shuffles was just plain wrong -- easily deceived through simple techniques.)

因此，我的问题是: 我如何分析我的洗牌算法(假设那里的 random:uniform()调用能够产生具有良好特征的适当随机数) ？我有什么数学工具可以用来判断，比如说，对一个范围为1的整数列表进行100,000次洗牌。。100已经给了我似乎很好的洗牌结果？我自己做了一些测试(例如，比较洗牌中的增量和减量) ，但是我想知道更多。

如果有任何关于洗牌算法本身的见解，我们也会很感激。

15635 次浏览
小开

正如 Wikipedia 文章中所讨论的，您的算法是基于排序的洗牌。

一般来说，基于排序的洗牌的计算复杂度与底层排序算法相同(例如，O (N log N)平均值，O (N2)快速排序的洗牌的最坏情况) ，尽管分布不是 perfectly一致的，但对于大多数实际目的来说，它应该接近一致。

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

which covers the limitations of sort-based shuffles in more detail, and also offers two adaptations of the Fischer–Yates strategy: a naive O(N²) one, and a binary-tree-based O(N log N) one.

遗憾的是，函数式编程世界不允许您访问可变状态。

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

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

附录

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

这种方法的主要缺点与其他任何无限键排序洗牌相同: 没有终止保证。虽然随着比较的进行，终止的可能性增加，但是没有一个上界: 最坏情况下的复杂度是 O (∞)。

小开
最佳答案

一般评论

我个人对概率算法正确性的看法是: 如果你知道如何使用 证明，那么它就是正确的; 如果你不知道，那么它肯定是错误的。

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

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

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

一般的想法是，随机使用算法探索一个世界的可能性的一部分。每次你的算法要求一个随机元素在一个集合({ true，false}当抛硬币时) ，有两个可能的结果为您的算法，其中之一是选择。您可以更改算法，以便它不返回一个可能的结果，而是并行地探索 所有解决方案，并返回所有可能的结果和相关的分布。

通常，这需要深入地重写算法。如果你的语言支持带分隔符的延续，你不必这样做; 你可以在函数内部实现“探索所有可能的结果”，要求一个随机元素(这个想法是随机生成器，不是返回一个结果，而是捕获与你的程序相关的延续，然后用所有不同的结果运行它)。有关这种方法的示例，请参见 Oleg 的 汉赛。

一个中间的解决方案，也许不那么神秘，就是将这个“可能结果的世界”表示为一个单子，并使用 Haskell 这样的语言和单子编程工具。下面是你的算法的一个变量1的实现例子，在哈斯克尔，使用了 概率包的概率单子:

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的列表中是统一的; 它可能仍然是错误的。

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

基于排序的洗牌

下面是一个简单的算法，我相信我能证明它是正确的:

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

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

如果你在[1]中选择你的钥匙。.其中 N 是集合的长度，会有很多碰撞(生日问题)。如果您选择的密钥是一个32位整数，那么实际上冲突的概率很低，但仍然受到生日问题的影响。

If you use infinite (lazily evaluated) bitstrings as keys, rather than finite-length keys, the probability of a collision becomes 0, and checking for distinctness is no longer necessary.

下面是 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))

There are other approaches to "pure shuffling". A nice one is apfelmus's 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调用之后，您就知道了每个列表的第一个元素，等等。当您的算法返回时，测试列表是完全已知的，并且根据这些列表元素是 sorted(按字典顺序排序，或者被认为是实数的二进制表示)。

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

The sort is uniform because the bitstrings are all different. Indeed, two elements with real numbers equal up to the n-th bit are on the same side of a partition occurring during a recursive shuffle call of depth n. The algorithm only terminates when all the lists resulting from partitions are empty or singletons : all elements have been separated by at least one test, and therefore have one distinct binary decimal.

随机终止

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

有可能的输出将使您的算法 分道扬镳，而不是终止。例如，如果随机数生成器总是输出 0，那么每个 partition调用将不变地返回输入列表，在该列表上递归地调用 shuffle: 您将无限期地循环。

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

  • 第一个 N 调用返回 true的概率是2 ^ {-N }
  • 所有调用返回 true的概率是对于所有 N，第一个 N 调用返回 0的事件的无限交集的概率; 它是2 ^ {-N }的最小限制1，即0

¹: for the mathematical details, see http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

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

因此，您知道您的算法 以概率1结束。这是一个稍微弱的保证，费舍尔-耶茨算法，其中 永远终止。尤其是，你很容易受到邪恶对手的攻击，他们会控制你的随机数生成器。

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

小开

我之前做过一些类似的工作，您可能对 Clojure 的向量特别感兴趣，它们是功能性的、不可变的，但仍然具有 O (1)随机访问/更新特性。这两个主题有几个“从这个 M 大小的列表中随机取 N 个元素”的实现; 如果你让 N = M，至少其中一个会变成 Fisher-Yates 的函数实现。

https://gist.github.com/805546

https://gist.github.com/805747

小开

基于 如何测试随机性(点-洗牌的情况) ，我建议:

Shuffle (中等大小)由相等数量的0和1组成的数组。重复并连接，直到无聊为止。将它们作为顽固测试的输入。如果你有一个很好的洗牌，那么你应该生成零和一的随机序列(需要注意的是，在中等大小的数组的边界上，零(或者一)的累积过量是零，你希望测试检测到，但是较大的“中等”是不太可能这样做)。

Note that a test can reject your shuffle for three reasons:

  • 洗牌算法很糟糕,
  • 洗牌程序或初始化过程中使用的随机数生成器不好，或者
  • 测试实现很糟糕。

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

Various adaptations of the 死硬测试 (to resolve certain numbers, I used the 来源 from the 顽固的主页). The principle mechanism of adaptation is to make the shuffle algorithm act as a source of uniformly distributed random bits.

  • 生日间隔: 在 N零的数组中，插入日志 N零。洗牌。一直重复，直到无聊为止。构建一个距离间的分布，与指数分布进行比较。您应该使用不同的初始化策略来执行这个实验——前面的、末尾的、中间的一起执行，以及随机分散的初始化策略。(后者的最大风险是初始化随机化不好(相对于洗牌随机化) ，导致洗牌被拒绝。)这实际上可以用相同值的块来完成，但问题是它在分布中引入了相关性(一和二不能在一次洗牌中处于同一位置)。
  • Overlapping permutations: shuffle five values a bunch of times. Verify that the 120 outcomes are about equally likely. (Chi-squared test, 119 degrees of freedom -- the diehard test (cdoperm5.c) uses 99 degrees of freedom, but this is (mostly) an artifact of sequential correlation caused by using overlapping subsequences of the input sequence.)
  • 矩阵的秩: 从2 * (6 * 8) ^ 2 = 4608位，从等数的0和1中选择6个不重叠的8位子字符串。把它们看作一个6乘8的二进制矩阵并计算它的秩。重复100,000个矩阵。(集合排名0-4。然后排名是6、5或0-4。)排名的预期 fraction为0.773118、0.217439、0.009443。卡方法与两自由度分数观测值的比较。31乘31和32乘32的测试是相似的。0-28和0-29的排名分别汇集在一起。期望分数是0.2887880952、0.5775761902、0.1283502644、0.0052854502。卡方检验有三个自由度。

诸如此类。

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


提交答案