Obtener un subconjunto aleatorio de un conjunto de F #

Question

Estoy tratando de pensar en una manera elegante de conseguir un subconjunto aleatorio de un conjunto de F #

¿Alguna idea sobre esto?

Tal vez esto funcionaría: decir que tenemos un conjunto de elementos 2 ^x y tenemos que escoger un subconjunto de los elementos y. Entonces, si pudiéramos generar un número aleatorio x de bits de tamaño que contiene exactamente Y 2 ⁿ poderes que efectivamente tenemos una máscara aleatoria con agujeros Y en el mismo. Podríamos seguir generando nuevos números aleatorios hasta que consigamos el primero satisfacer esta restricción, pero ¿hay una manera mejor?

Answer 1

Si no desea convertir en una matriz que podría hacer algo como esto. Esto es O (n * m) donde m es el tamaño del conjunto.

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

De acuerdo con @JohannesRossel. Hay un F # aleatoria-un-array algoritmo aquí que pueda modificar adecuadamente. Convertir el conjunto en una matriz, y luego bucle hasta que haya seleccionado suficientes elementos aleatorios para el nuevo subconjunto.

Answer 3

No tener una muy buena comprensión de F # y lo que podría ser considerado elegante ahí, sólo podría hacer una reproducción aleatoria en la lista de elementos y seleccione el primer y. Fisher-Yates barajar incluso le ayuda en este sentido ya que también sólo tiene que mezclar y elementos.

Answer 4

rnd debe estar fuera de la función de subconjuntos.

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

¿Se refiere a un subconjunto aleatorio de cualquier tamaño?

En el caso de un subconjunto aleatorio de un tamaño específico, hay una respuesta muy elegante aquí:

seleccione N elementos azar de una lista en C #

Aquí está en pseudocódigo:

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

Uso Seq.fold para construir usando la evaluación perezosa azar sub-conjunto:

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)