Walker Alias implementation converted from java implementation found at http://ramen.physics.und.edu/~yloh/RESOURCES/wamdemo.java

WalkerAlias.cs

using System;

namespace WeightedSetSelection
{
    public class WalkerAlias
	{
		Random random;
		public int N; public double[] ff; public int[] aliasTable;

		public WalkerAlias(int N, double[] pp) // pp=probability vector
		{
			int i, j, jmin, jmax;
			double bmin, bmax, s, oon, tol = 1E-15d;
			double[] bb = new double[N];
			random = new Random();
			this.N = N;
			ff = new double[N];
			aliasTable = new int[N];
			oon = 1.0d / N;

			//----- Verify that user-supplied pp[]'s sum to unity! (this doesn't apply in our case)
			//s = 0;
			//for (i = 0; i < N; i++)
			//	s += pp[i];
			//if (Math.Abs(s - 1) > tol)
			//	throw new InvalidOperationException("Not norm!");

			//----- Set up arrays
			for (i = 0; i < N; i++)
			{
				bb[i] = pp[i] - oon;
				aliasTable[i] = i;
				ff[i] = 1.0;
			}

			for (i = 0; i < N; i++)
			{
				bmin = +1E10;
				jmin = -1;
				bmax = -1E10;
				jmax = -1;

				for (j = 0; j < N; j++)
				{
					if (bmin > bb[j]) { bmin = bb[j]; jmin = j; }
					if (bmax < bb[j]) { bmax = bb[j]; jmax = j; }
				}

				if (bmax - bmin < tol) break;

				aliasTable[jmin] = jmax;
				ff[jmin] = 1 + bmin * N;
				bb[jmin] = 0;
				bb[jmax] = bmax + bmin;
			}

		}

		public void DumpInternals(double[] pp)
		{
			Console.WriteLine("\ni \tpp[i] \tff[i] \t1-f\taa[i]");
			for (int i = 0; i < N; i++)
			{
				Console.WriteLine(i + "\t" + pp[i] + "\t" +
						Math.Round(100 * ff[i])
						+ "%\t" +
						Math.Round(100 * (1 - ff[i]))
						+ "%\t" + aliasTable[i]);
			}

		}

		public int sample()
		{
			int n = random.Next(N);
			if (random.NextDouble() > ff[n])
				n = aliasTable[n];
			return n;
		}
	}
}