Holen Sie sich eine zufällige Teilmenge von einem Set in F#

Question

Ich versuche mir eine elegante Art zu denken, eine zufällige Teilmenge von einem Set in F# zu erhalten

Irgendwelche Gedanken dazu?

Vielleicht würde das funktionieren: Angenommen, wir haben einen Satz von 2^x Elemente und wir müssen eine Untergruppe von Y -Elementen auswählen. Wenn wir dann eine X -Größe -Zufallszahl von X -Größe generieren könnten, die genau Y 2 enthältⁿ Kräfte, die wir effektiv eine zufällige Maske mit Y -Löchern haben. Wir könnten weiterhin neue Zufallszahlen generieren, bis wir den ersten bekommen, der diese Einschränkung befriedigt, aber gibt es einen besseren Weg?

Answer 1

Wenn Sie nicht in ein Array konvertieren möchten, können Sie so etwas tun. Dies ist o (n*m), wobei m die Größe des Satzes hat.

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

Stimmen Sie @johannesrossel zu. Es gibt einen F# Shuffle-Anarray-Algorithmus hier Sie können sich angemessen ändern. Konvertieren Sie das Set in ein Array und schalten Sie dann auf, bis Sie genügend zufällige Elemente für die neue Teilmenge ausgewählt haben.

Answer 3

Wenn Sie kein wirklich gutes Verständnis für F# haben und was dort als elegant angesehen werden könnte y. EIN Fisher-yates Shuffle Hilft Ihnen in dieser Hinsicht sogar, da Sie auch nur mischen müssen y Elemente.

Answer 4

RND muss außerhalb der Untergruppe 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

Meinst du eine zufällige Teilmenge einer Größe?

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

Wählen Sie n zufällige Elemente aus einer Liste ausu003CT> in C#

Hier ist es in 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

Verwenden von seq.fold zum Konstrukt mit einer faulen Bewertung zufälliger Untereinsatz:

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)