Holen Sie sich einen zufällig ausgewählten Untergruppe von einem Satz in F #

Question

ich eine elegante Art und Weise zu denken, ich versuche, von einem Satz in F # eine zufällige Teilmenge des Erhaltens

Irgendwelche Gedanken dazu?

Vielleicht würde das funktionieren: sagen wir haben einen Satz von 2 ^x Elemente und wir müssen eine Teilmenge von y-Elemente auswählen. Wenn wir dann eine x-große Bit-Zufallszahl erzeugen könnten, die genau y 2 ⁿ enthält, haben wir effektiv eine zufällige Maske mit y-Löchern darin. Wir könnten weiterhin neue Zufallszahlen generieren, bis wir die erste haben, die diese Einschränkung erfüllt, aber gibt es einen besseren Weg?

Answer 1

Wenn Sie nicht in ein Array konvertieren möchten, könnten Sie so etwas tun. Dies ist O (n * m), wobei m die Größe der Menge ist.

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

Da Sie F # nicht wirklich gut verstehen und was dort als elegant betrachtet werden könnte, können Sie einfach die Liste der Elemente mischen und die erste y auswählen. Ein Fisher-Yates shuffle hilft Ihnen sogar in dieser Hinsicht, da Sie auch nur y Elemente mischen müssen.

Answer 3

Stimmen Sie mit @JohannesRossel überein. Es gibt einen F # Shuffle-a-Array-Algorithmus here, den Sie entsprechend modifizieren können. Konvertieren Sie das Set in ein Array und wiederholen Sie die Schleife, bis Sie genügend zufällige Elemente für die neue Teilmenge ausgewählt haben.

Answer 4

rnd muss aus der Teilmengenfunktion sein.

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

Seq.fold Verwendung mit lazy evaluation zufällig ausgewählten Untergruppe zu konstruieren:

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) 

Answer 6

Sie eine zufällige Teilmenge jeder Größe bedeuten Sie?

Für den Fall einer zufälligen Teilmenge einer bestimmten Größe, gibt es eine sehr elegante Antwort hier:

Select N random elements from a List<T> in C#

es hier in Pseudo-Code ist:

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