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

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

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

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

источник

2009-07-14 Anonymous

Если вы не хотите конвертировать в массив, вы можете сделать что-то вроде этого. Это 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

источник

2009-07-14 17:58:57 gradbot

Поскольку этот подход неизбежно выполняется плохо, вам лучше преобразовать его в массив, перетасовать, а затем перенести первые результаты в виде набора - его, вероятно, легче читать для загрузки. И если вы _really_ не хотите преобразовывать свой исходный набор в массив, вы все равно можете создать случайную логическую маску, используя подходящий перетасованный массив (с m true и nm false), а затем просто zip массив с набором, фильтровать по маскам и отображать обратно в набор - без преобразования исходного набора в массив и сохранения производительности O (n). –

Ваш фрагмент кода обычно дает мне тот же набор элементов, за исключением последнего. Я получил 4 раза: '[0; 1; 5], [0; 1; 6], [0; 1; 2], [0; 1; 4] '. Очевидно, ** это не случайное ** подмножество. И это происходит из-за этой линии 'yield! set |> Set.remove i' –

'yield!' дает все элементы последовательности, в этом случае исходный набор с одним удаленным элементом ('set |> Set.remove i'), что неверно. Функция должна быть рекурсивной ('let rec randomSubSet n set = ...'), и вы должны «уступить! set |> Set.remove i |> randomSubSet (n-1) '. –

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

источник

2009-07-14 10:07:35 Joey

F # наборы не позволяют для случайного времени доступа O (1), поэтому этот алгоритм будет неэффективным без преобразования множества в массив. – gradbot

Хорошо, было бы так же сложно, как и ваше решение, если я правильно это увижу. Но у вас есть код, мне пока не удалось изучить F #, так что вы получите мой +1 :) – Joey

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

источник

2009-07-14 11:42:41 Brian

Кажется, что @usernameIdentifier - это общее соглашение здесь для ссылки на других (что, я считаю, было кооптировано из другого средний), поэтому я просто пытаюсь пойти с потоком. – Brian

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

источник

2009-07-22 11:17:52

Использование 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)

источник

2009-07-22 12:04:15

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

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

Select N random elements from a List<T> in 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

источник

2010-05-02 20:41:26 dreeves

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

ответ

Смежные вопросы