Ottenere un sottoinsieme casuale da un set in F #
Domanda
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 n 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?
Soluzione
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
Altri suggerimenti
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.
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.
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
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
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
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)