4

我正在尝试一种优雅的方式从 F# 中的集合中获取随机子集

对此有什么想法吗?

也许这会起作用:假设我们有一组 2 x元素,我们需要选择 y 元素的子集。然后,如果我们可以生成一个 x 大小的位随机数,它正好包含 y 2 n次幂,我们实际上就有了一个带有 y 个孔的随机掩码。我们可以继续生成新的随机数,直到我们得到第一个满足这个约束的随机数,但有更好的方法吗?

4

6 回答 6

2

没有很好地掌握 F# 以及那里可能被认为是优雅的东西,你可以在元素列表上做一个随机播放并选择第一个y。Fisher-Yates shuffle甚至可以在这方面为您提供帮助,因为您也只需要 shuffle y元素

于 2009-07-14T10:07:35.327 回答
2

同意@JohannesRossel。这里有一个 F# shuffle-an-array 算法您可以适当修改。将 Set 转换为数组,然后循环,直到为新子集选择了足够的随机元素。

于 2009-07-14T11:42:41.653 回答
2

如果您不想转换为数组,则可以执行以下操作。这是 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    
于 2009-07-14T17:58:57.267 回答
1

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
于 2009-07-22T11:17:52.590 回答
1

您是指任意大小的随机子集吗?

对于特定大小的随机子集,这里有一个非常优雅的答案:

从 C# 中的 List<T> 中选择 N 个随机元素

这是伪代码:

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
于 2010-05-02T20:41:26.737 回答
0

使用 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)
于 2009-07-22T12:04:15.600 回答