如何在OCaml的O（n）中随机播放列表？ [英] How to shuffle list in O(n) in OCaml?

问题描述

$ b $如何为OCaml中的 list 添加O（n）？

---

要求：

1. 无数组或原地使用

li>

将此视为面试问题 不可变的，而且通常需要支付 log n 价格才能处理不可变数据。如果您愿意支付这笔费用，则有一个明显的方法：使用随机值标记每个列表元素，根据随机值进行排序，删除随机值。这是我在生产代码中对列表进行洗牌的方式。





以下是我销售的iOS应用程序中的洗牌代码：

  let shuffle d = 
 let nd = List.map（fun c  - >（Random.bits（），c））d in 
让sond = List.sort比较nd in 
 List.map snd sond 
  




It is not hard to shuffle an array in O(n), with in place swapping,

How to do it for list in OCaml, with O(n)?

---

Requirement:

1. No array or in place usage

2. Consider this as an interview question

解决方案

Lists are immutable, and there's often a log n price to pay for working with immutable data. If you're willing to pay this cost, there's an obvious n log n approach: tag each list element with a random value, sort based on random value, remove random values. This is the way I shuffle lists in my production code.

Here is the shuffle code from the iOS apps that I sell:

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

这篇关于如何在OCaml的O（n）中随机播放列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！