题
我正在尝试想一种优雅的方式从 F# 中的集合中获取随机子集
对此有什么想法吗?
也许这会起作用:假设我们有 2 件套X 元素,我们需要选择 y 元素的子集。那么如果我们可以生成一个 x 大小的位随机数,其中恰好包含 y 2n 我们实际上拥有一个带有 y 个孔的随机掩模。我们可以不断生成新的随机数,直到得到第一个满足此约束的随机数,但是有更好的方法吗?
解决方案
如果您不想转换成数组,你可以做这样的事情。这是O(n * m),其中m是集的大小。
open System
let rnd = Random(0);
let set = Array.init 10 (fun i -> i) |> Set.of_array
let randomSubSet n set =
seq {
let i = set |> Set.to_seq |> Seq.nth (rnd.Next(set.Count))
yield i
yield! set |> Set.remove i
}
|> Seq.take n
|> Set.of_seq
let result = set |> randomSubSet 3
for x in result do
printfn "%A" x
其他提示
同意@JohannesRossel。这里有一个F#洗牌的阵列算法这里可以适当地修改。转换成一阵列,然后循环,直到你选择的新子集足够的随机元素。
如果没有很好地掌握 F# 以及那里可能被认为优雅的内容,您可以在元素列表上进行随机播放并选择第一个 y。 A 费舍尔-耶茨洗牌 甚至在这方面可以帮助你,因为你也只需要洗牌 y 元素。
RND必须走出子集的功能。
let rnd = new Random()
let rec subset xs =
let removeAt n xs = ( Seq.nth (n-1) xs, Seq.append (Seq.take (n-1) xs) (Seq.skip n xs) )
match xs with
| [] -> []
| _ -> let (rem, left) = removeAt (rnd.Next( List.length xs ) + 1) xs
let next = subset (List.of_seq left)
if rnd.Next(2) = 0 then rem :: next else next
你的意思是任何大小的随机子集?
有关特定大小的随机子集的情况下,这里是一个非常优雅的回答:
下面是在伪代码:
RandomKSubset(list, k):
n = len(list)
needed = k
result = {}
for i = 0 to n:
if rand() < needed / (n-i)
push(list[i], result)
needed--
return result
使用Seq.fold使用构建惰性计算随机子集:
let rnd = new Random()
let subset2 xs = let insertAt n xs x = Seq.concat [Seq.take n xs; seq [x]; Seq.skip n xs]
let randomInsert xs = insertAt (rnd.Next( (Seq.length xs) + 1 )) xs
xs |> Seq.fold randomInsert Seq.empty |> Seq.take (rnd.Next( Seq.length xs ) + 1)
不隶属于 StackOverflow