Get a random subset from a set in F #

Question

I'm trying to think of an elegant way to get a random subset from a set in F #

Any thoughts on this?

Perhaps this would work: let's say we have a set of 2 ^x elements and we need to select a subset of y elements. Then, if we could generate a random number of bits of size x that contains exactly y 2 ⁿ power, we effectively have a random mask with y holes in it. We could generate new random numbers until we get the first one satisfying this restriction, but is there a better way?

Answer 1

If you do not want to convert to an array, you can do something like this. This is O (n * m), where m is the size of the set.

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 

Answer 2

Without a really good understanding of F # and what can be considered elegant, you can simply shuffle in the list of items and select the first y. A Fisher-Yates shuffle even helps you in this regard, since you also just need to shuffle the y elements.

Answer 3

Agree with @JohannesRossel. Here you can change the appropriate F # shuffle-a-array algorithm here . Convert Set to an array and then a loop until you select enough random elements for the new subset.

Answer 4

rnd must be outside the function of the subset.

 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 

Answer 5

Do you mean a random subset of any size?

In the case of a random subset of a certain size, here is a very elegant answer:

Select N random items from <T> in C #

Here it is in pseudocode:

 RandomKSubset(list, k): n = len(list) needed = k result = {} for i = 0 to n: if rand() < needed / (ni) push(list[i], result) needed-- return result 

Answer 6

Using Seq.fold to build using lazy random sampling:

 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)