Weighted random selection using Walker's Alias Method

Question

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);
        }
    }
}

if anyone can remake it in F# please post your code

If you have an answer to a question, it's generally considered good practice to ask the question and then respond to the question yourself (but not by adding the answer in the question). See http://blog.stackoverflow.com/2008/07/stack-overflow-private-beta-begins/ and http://meta.stackexchange.com/questions/17463/can-i-answer-my-own-questions-even-those-where-i-knew-the-answer-before-asking — Abel, Apr 15 '12 at 18:11
I'm not sure why you think this Walker's alias method, but it is not even remotely close to that method. Indeed you require O(N) to pick one out of N element, when the alias method allows you to draw a random object in O(1) time by creating a two-line array. — Jérémie, May 08 '12 at 19:40
@Jeremie I was looking for this for some time, and found only python implementation which I don't understand, but after reading the intro for those codes I got to this, which actually worked — Omu, May 08 '12 at 21:11
@Chuck Norris, yes it does work and it's probably more practical like that... but it's much, much slower than if you were using something like the actual Alias Method, because you have to go through the whole dictionary every time you make a random selection. Think of it as the difference between looking up an element in an unsorted list, and in a hash table. — Jérémie, May 08 '12 at 21:18
@Jeremie do you have a c#/f# implementation of the actual Walker alias method ? — Omu, Jun 13 '12 at 12:55
Here is a Ruby implementation: https://github.com/cantino/walker_method — Andrew, Mar 05 '13 at 07:19
This is **NOT** walkers alias method. This requires O(n) time to complete. — Andreas, Oct 04 '14 at 19:21

score 6 · Accepted Answer · edited Apr 16 '12 at 16:47

6

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)]

edited Apr 16 '12 at 16:47

ildjarn

62,044
9
127
211

answered Apr 15 '12 at 17:57

Brian

117,631
17
236
300

pad · Answer 2 · 2012-04-18T17:58:11.743

open System

let oo = dict [ "A", 7;
                "B", 1;
                "C", 9;
                "D", 8;
                "E", 11 ]

let rnd = Random()
let pick = oo.Values |> Seq.sum |> rnd.Next

let res = oo |> Seq.scan (fun (_, s) (KeyValue(k, v)) -> k, s + v) ("", 0)
             |> Seq.tryPick (fun (k, s) -> if s >= pick 
                                           then printfn "Result is %s" k; Some k 
                                           else None)

Weighted random selection using Walker's Alias Method

2 Answers2

Linked