F#의 세트에서 임의의 하위 집합을 가져옵니다.

Question

나는 F#의 세트에서 임의의 하위 집합을 얻는 우아한 방법을 생각하려고합니다.

이것에 대한 생각이 있습니까?

아마도 이것은 효과가있을 것입니다 : 우리는 2 세트가 있다고 가정 해^엑스 요소와 우리는 Y 요소의 하위 집합을 선택해야합니다. 그런 다음 정확히 y 2를 포함하는 X 크기 비트 랜덤 번호를 생성 할 수 있다면^N 힘은 효과적으로 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#을 정말 잘 이해하지 못하고 우아한 것으로 간주 될 수있는 것은 요소 목록에서 셔플을하고 첫 번째를 선택할 수 있습니다. 와이. ㅏ Fisher-Yates Shuffle 당신은 또한 당신이 셔플하기 만하면서이 점에서 당신을 도와줍니다. 와이 집단.

Answer 4

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 5

크기의 임의의 하위 집합을 의미합니까?

특정 크기의 임의의 하위 집합의 경우 여기에는 매우 우아한 대답이 있습니다.

목록에서 n 랜덤 요소를 선택하십시오u003CT> C#에서

여기에는 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

게으른 평가 랜덤 하위 세트를 사용하여 구조적으로 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)