Obtenha um subconjunto aleatório de um conjunto em f#

Question

Estou tentando pensar em uma maneira elegante de obter um subconjunto aleatório de um conjunto em f#

Alguma ideia sobre isso?

Talvez isso funcione: digamos que temos um conjunto de 2^x elementos e precisamos escolher um subconjunto de elementos Y. Então, se pudéssemos gerar um número aleatório de tamanho X que contém exatamente 2ⁿ Poderes, efetivamente temos uma máscara aleatória com os furos. Poderíamos continuar gerando novos números aleatórios até obtermos o primeiro satisfazendo essa restrição, mas existe uma maneira melhor?

Answer 1

Se você não quiser se converter em uma matriz, poderá fazer algo assim. Este é o O (n*m), onde m é o tamanho do 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

Concordo com @Johannesrossel. Há um algoritmo F# Shuffle-an-Array aqui Você pode modificar adequadamente. Converta o conjunto em uma matriz e, em seguida, faça um loop até selecionar elementos aleatórios suficientes para o novo subconjunto.

Answer 3

Não tendo uma compreensão muito boa do F# e o que pode ser considerado elegante lá, você pode simplesmente fazer um shuffle na lista de elementos e selecionar o primeiro y. UMA Fisher-Yates Shuffle até ajuda você nesse aspecto, pois você também só precisa embaralhar y elementos.

Answer 4

O RND deve estar fora da função do subconjunto.

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

Você quer dizer um subconjunto aleatório de qualquer tamanho?

Para o caso de um subconjunto aleatório de um tamanho específico, há uma resposta muito elegante aqui:

Selecione n elementos aleatórios de uma listau003CT> em C#

Aqui está em 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

Usando seq.fold para construir usando uma avaliação preguiçosa subconfet aleatória:

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)