一般说明
我个人关于概率使用算法正确性的方法：如果你知道如何证明它是正确的，那么它可能是正确的；如果你不这样做，那肯定是错误的。
换句话说，尝试分析你能想出的每一种算法通常是没有希望的：你必须不断地寻找一种算法，直到你找到一个可以证明是正确的算法。
通过计算分布来分析随机算法
我知道一种“自动”分析洗牌（或更一般地说是随机使用算法）的方法，它比简单的“进行大量测试并检查一致性”更强。您可以机械地计算与算法的每个输入相关的分布。
总的想法是随机使用算法探索可能性世界的一部分。每次您的算法要求集合中的随机元素（掷硬币时{ 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..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 个惰性流是否不同，以及运行时间更高的概率成倍下降。