从F＃中的集合中获取随机子集

I am trying to think of an elegant way of getting a random subset from a set in F#

我试图想一个从F#中的集合中获取随机子集的优雅方式

Any thoughts on this?

有什么想法吗?

Perhaps this would work: say we have a set of 2^x elements and we need to pick a subset of y elements. Then if we could generate an x sized bit random number that contains exactly y 2ⁿ powers we effectively have a random mask with y holes in it. We could keep generating new random numbers until we get the first one satisfying this constraint but is there a better way?

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

6 个解决方案

#1

If you don't want to convert to an array you could do something like this. This is O(n*m) where m is the size of the set.

如果你不想转换为数组,你可以做这样的事情。这是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

#2

Agree with @JohannesRossel. There's an F# shuffle-an-array algorithm here you can modify suitably. Convert the Set into an array, and then loop until you've selected enough random elements for the new subset.

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

#3

Not having a really good grasp of F# and what might be considered elegant there, you could just do a shuffle on the list of elements and select the first y. A Fisher-Yates shuffle even helps you in this respect as you also only need to shuffle y elements.

没有很好地掌握F#以及可能被认为优雅的东西,你可以在元素列表上进行一次洗牌并选择第一个y。在这方面,Fisher-Yates shuffle甚至可以帮助你,因为你也只需要改变y元素。

#4

rnd must be out of subset function.

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

#5

Do you mean a random subset of any size?

你的意思是任何大小的随机子集?

For the case of a random subset of a specific size, there's a very elegant answer here:

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

Select N random elements from a List<T> in C#

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

Here it is in pseudocode:

这是伪代码:

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

#6

Using Seq.fold to construct using lazy evaluation random sub-set:

使用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)

#1