Ottenere un sottoinsieme casuale da un set in F #

Question

Sto cercando di pensare ad un modo elegante di ottenere un sottoinsieme casuale da un set in F #

Ogni pensiero su questo?

Forse questo dovrebbe funzionare: dire che abbiamo un set di 2 ^x elementi e abbiamo bisogno di scegliere un sottoinsieme di elementi y. Quindi se si potesse generare un numero casuale bit x dimensioni che contiene esattamente y 2 ⁿ potenze abbiamo efficacemente una maschera casuale con fori y in esso. Potremmo continuare a generare nuovi numeri casuali fino a quando si ottiene il primo soddisfare questo vincolo, ma c'è un modo migliore?

Answer 1

Se non si desidera convertire in una matrice si potrebbe fare qualcosa di simile. Questo è O (n * m) dove m è la dimensione del 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

D'accordo con @JohannesRossel. C'è un riordino-an-array algoritmo di F # qui è possibile modificare opportunamente. Convertire il set in un array, e quindi ciclo fino a quando è stato selezionato elementi casuali sufficienti per il nuovo sottoinsieme.

Answer 3

Non avendo una buona padronanza di F # e quello che potrebbe essere considerato elegante lì, si può solo fare un riordino nella lista degli elementi e selezionare la prima a. A Fisher-Yates mischiare anche ti aiuta in questo senso, come si anche solo bisogno di mischiare y elementi.

Answer 4

RND deve essere fuori della funzione sottoinsieme.

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

Vuoi dire un sottoinsieme casuale di qualsiasi dimensione?

Per il caso di un sottoinsieme casuale di una dimensione specifica, non c'è una risposta molto elegante qui:

Selezionare N elementi casuali da una lista in C #

Qui è in pseudocodice:

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 realizzabili con valutazione pigra casuale sottoinsieme:

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)