functional-programming - 如何在 OCaml 中的 O(n) 中洗牌？

Question

array通过就地交换，在 O(n) 中洗牌并不难，

如何list在 OCaml 中使用 O(n) 执行此操作？

---

要求：

1. 没有阵列或就地使用

2. 将此视为面试问题

Answer 1

列表是不可变的，使用不可变数据通常需要付出log n的代价。如果您愿意支付此费用，则有一个明显的n log n方法：用随机值标记每个列表元素，根据随机值排序，删除随机值。这就是我在生产代码中随机播放列表的方式。

这是我销售的 iOS 应用程序的随机播放代码：

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond

Answer 2

您可以模仿卡片的浅滩洗牌。

一副纸牌的洗牌意味着：

• 将甲板分成两部分
• 将两部分交错

做反向排列实际上更容易：

• 有两个辅助列表 A 和 B，遍历原始列表 L 并将每个元素随机（概率为 1/2）推到 A 或 B 前面。
• L := List.rev A @ List.rev B（这可以使用自定义 List.rev 进行尾递归）。
• 重复k次。

根据“Persi Diaconis，2002 年对浅滩洗牌分析的数学发展”，选择 k = 3/2 log_2(n) + c。事实上，均匀性和结果之间的总变化距离呈指数快速下降到 0：每次增加 c 时它大约减半。您可以选择 c=10。

空间 O(1)（如果你破坏 L），时间 O(n log n)。但是对随机生成器有 O(n log n) 次调用，而 Jeffrey Scofield 的解决方案只需要 O(n) 个随机位，但需要 Θ(n) 个空间。