Obtenez un sous-ensemble aléatoire d'un ensemble en F #

Question

Je suis en train de penser à une façon élégante d'obtenir un sous-ensemble aléatoire d'un ensemble en F #

Les réflexions sur ce sujet?

Peut-être que cela fonctionnerait: dire que nous avons un ensemble de 2 ^x et nous devons choisir un sous-ensemble d'éléments y. Ensuite, si nous pouvions générer un x taille nombre de bits aléatoires qui contient exactement les pouvoirs y 2 ⁿ nous avons effectivement un masque aléatoire avec des trous y en elle. Nous pourrions continuer à générer de nouveaux nombres aléatoires jusqu'à ce que nous obtenons la première satisfaction de cette contrainte, mais est-il une meilleure façon?

Answer 1

Si vous ne voulez pas convertir à un tableau que vous pourriez faire quelque chose comme ça. Ceci est O (n * m) où m est la taille de l'ensemble.

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

D'accord avec @JohannesRossel. Il y a un F # algorithme aléatoire-un-tableau ici vous pouvez modifier de façon appropriée. Convertir le Set dans un tableau, puis en boucle jusqu'à ce que vous avez sélectionné des éléments aléatoires suffisamment pour le nouveau sous-ensemble.

Answer 3

Ne pas avoir une très bonne connaissance de F # et ce qui pourrait être considéré comme il élégant, vous pouvez simplement faire un remaniement sur la liste des éléments et sélectionnez la première y. A Fisher-Yates vous aide lecture aléatoire même à cet égard que vous aussi avez seulement besoin de mélanger y éléments.

Answer 4

rnd doit être hors de la fonction sous-ensemble.

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

Voulez-vous dire un sous-ensemble aléatoire de toute taille?

Pour le cas d'un sous-ensemble aléatoire d'une taille spécifique, il y a une réponse très élégante ici:

Sélectionnez N éléments aléatoires à partir d'une liste en C #

Ici, il est en 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

Answer 6

Utilisation Seq.fold pour construire à l'aide sous-ensemble aléatoire d'évaluation paresseuse:

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)