4

F＃のセットからランダムなサブセットを取得するエレガントな方法を考えようとしています

これについて何か考えはありますか？

おそらくこれはうまくいくでしょう：2つのx要素のセットがあり、y要素のサブセットを選択する必要があるとします。次に、正確にy 2 n乗を含むxサイズのビット乱数を生成できれば、y個の穴があるランダムマスクが効果的に得られます。この制約を満たす最初の乱数が得られるまで、新しい乱数を生成し続けることができますが、より良い方法はありますか？

4

6 に答える 6

2

@JohannesRosselに同意します。ここには、適切に変更できるF# shuffle-an-array アルゴリズムがあります。Set を配列に変換し、新しいサブセットに十分なランダム要素を選択するまでループします。

于 2009-07-14T11:42:41.653 に答える
2

F# とそこでエレガントと見なされるものをよく理解していない場合は、要素のリストをシャッフルして最初のy を選択するだけで済みます。y要素をシャッフルするだけでよいため、フィッシャー・イェーツ・シャッフルはこの点でも役立ちます。

于 2009-07-14T10:07:35.327 に答える
1

任意のサイズのランダムなサブセットを意味しますか?

特定のサイズのランダムなサブセットの場合、非常にエレガントな答えがここにあります:

C# で List<T> から N 個のランダムな要素を選択する

ここに疑似コードがあります：

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-02T20:41:26.737 に答える
1

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-22T11:17:52.590 に答える
0

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-22T12:04:15.600 に答える