加权随机选择使用沃克的别名方法 [英] Weighted random selection using Walker's Alias Method

问题描述

我一直在寻找这种算法
（算法，将随机元素的列表，其中每个元素都有被采摘不同的概率选择（重量））的
，发现只有Python和C的实现，在我做了一个C＃的，有点不同（但我想更简单），我想我应该分享，我也需要一个 F＃imlementation ，如果任何人都可以把它请张贴的答案

I was looking for this algorithm
(algorithm which will randomly select from a list of elements where each element has different probability of being picked (weight) )
and found only python and c implementations, after I did a C# one, a bit different (but I think simpler) I thought I should share it, also I need an F# imlementation, if anyone can make it please post an answer

using System;
using System.Collections.Generic;
using System.Linq;

namespace ChuckNorris
{
    class Program
    {
        static void Main(string[] args)
        {
            var oo = new Dictionary<string, int>
                         {
                             {"A",7},
                             {"B",1},
                             {"C",9},
                             {"D",8},
                             {"E",11},
                         };

            var rnd = new Random();
            var pick = rnd.Next(oo.Values.Sum());

            var sum = 0;
            var res = "";

            foreach (var o in oo)
            {
                sum += o.Value;
                if(sum >= pick)
                {
                    res = o.Key;
                    break;
                }
            }

            Console.WriteLine("result is "+  res);
        }
    }
}

如果任何人都可以在F＃中改造它，请发表您的code

推荐答案

下面是类似code F＃中：

Here is the similar code in F#:

let rng = new System.Random()
let d = [| "A", 3
           "B", 2
           "C", 3 |]
let sums = Seq.scan (+) 0 (dict d).Values |> Seq.skip 1 |> Seq.toArray 
let pick = rng.Next(sums.[sums.Length-1])
let res = fst d.[sums |> Seq.findIndex ((<) pick)]

这篇关于加权随机选择使用沃克的别名方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！