Получить случайное подмножество из набора в F #

Question

Я пытаюсь придумать элегантный способ получения случайного подмножества из набора в F #

Есть мысли по этому поводу?

Возможно, это сработает: скажем, у нас есть набор из 2 ^x элементов, и нам нужно выбрать подмножество из y элементов. Тогда, если бы мы могли сгенерировать битовое случайное число размером x, которое содержит ровно y 2 ⁿ степеней, у нас фактически была бы случайная маска с y отверстиями в ней. Мы могли бы продолжать генерировать новые случайные числа, пока не получим первое, удовлетворяющее этому ограничению, но есть ли лучший способ?

Answer 1

Если вы не хотите преобразовывать в массив, вы можете сделать что-то вроде этого. Это O (n * m), где m - размер множества.

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

Согласен с @JohannesRossel. Есть алгоритм F # shuffle-an-array здесь , который вы можете изменить соответствующим образом. Преобразуйте набор в массив, а затем зацикливайте, пока не выберите достаточно случайных элементов для нового подмножества.

Answer 3

Не имея действительно хорошего понимания F # и того, что там можно считать изящным, вы можете просто сделать перемешивание в списке элементов и выбрать первый y. A Fisher-Yates shuffle даже помогает вам в этом отношении, поскольку вам также нужно перетасовать y элементов.

Answer 4

Вы имеете в виду случайное подмножество любого размера?

Для случайного подмножества определенного размера, здесь есть очень элегантный ответ:

Выберите N случайных элементов из списка в C #

Вот оно в псевдокоде:

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 5

rnd должен быть вне функции подмножества.

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 6

Использование Seq.fold для построения с использованием случайного поднабора ленивых вычислений:

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)