Получаем случайное подмножество из набора в F#
Вопрос
Я пытаюсь придумать элегантный способ получения случайного подмножества из набора в F#
Есть какие-нибудь мысли по этому поводу?
Возможно, это сработало бы:допустим, у нас есть набор из 2x элементы, и нам нужно выбрать подмножество y элементов.Тогда, если бы мы могли сгенерировать битовое случайное число размером x, которое содержит ровно y 2n полномочия у нас фактически есть случайная маска с y отверстиями в ней.Мы могли бы продолжать генерировать новые случайные числа до тех пор, пока не получим первое, удовлетворяющее этому ограничению, но есть ли лучший способ?
Решение
Если вы не хотите преобразовывать в массив, вы могли бы сделать что-то вроде этого.Это 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
Другие советы
Согласен с @JohannesRossel.Существует алгоритм F # перетасовки массива здесь вы можете внести соответствующие изменения.Преобразуйте набор в массив, а затем выполняйте цикл до тех пор, пока не будет выбрано достаточное количество случайных элементов для нового подмножества.
Не имея действительно хорошего представления о F # и о том, что там можно считать элегантным, вы могли бы просто выполнить перетасовку в списке элементов и выбрать первый y. A Фишер-Йейтс перетасовывает даже помогает вам в этом отношении, так как вам также нужно только перетасовать y элементы.
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
Вы имеете в виду случайное подмножество любого размера?
Для случая случайного подмножества определенного размера здесь есть очень элегантный ответ:
Выберите N случайных элементов из списка<T> в 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
Использование 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)