如何在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