c#中奖算法的实现

原创 2016-11-10 14:46:03 576
摘要:算法名称 Alias Methodpublic class AliasMethod {        /* The probability and alias tables. */     

算法名称 Alias Method

public class AliasMethod {        /* The probability and alias tables. */
        private int[] _alias;        private double[] _probability;        public AliasMethod(List<Double> probabilities) {            /* Allocate space for the probability and alias tables. */
            _probability = new double[probabilities.Count];
            _alias = new int[probabilities.Count];            /* Compute the average probability and cache it for later use. */
            double average = 1.0 / probabilities.Count;            /* Create two stacks to act as worklists as we populate the tables. */
            var small = new Stack<int>();            var large = new Stack<int>();            /* Populate the stacks with the input probabilities. */
            for (int i = 0; i < probabilities.Count; ++i) {                /* If the probability is below the average probability, then we add
                 * it to the small list; otherwise we add it to the large list.                 */
                if (probabilities[i] >= average)
                    large.Push(i);                else
                    small.Push(i);
            }            /* As a note: in the mathematical specification of the algorithm, we
             * will always exhaust the small list before the big list.  However,
             * due to floating point inaccuracies, this is not necessarily true.
             * Consequently, this inner loop (which tries to pair small and large
             * elements) will have to check that both lists aren't empty.             */
            while (small.Count > 0 && large.Count > 0) {                /* Get the index of the small and the large probabilities. */
                int less = small.Pop();                int more = large.Pop();                /* These probabilities have not yet been scaled up to be such that
                 * 1/n is given weight 1.0.  We do this here instead.                 */
                _probability[less] = probabilities[less] * probabilities.Count;
                _alias[less] = more;                /* Decrease the probability of the larger one by the appropriate
                 * amount.                 */
                probabilities[more] = (probabilities[more] + probabilities[less] - average);                /* If the new probability is less than the average, add it into the
                 * small list; otherwise add it to the large list.                 */
                if (probabilities[more] >= average)
                    large.Push(more);                else
                    small.Push(more);
            }            /* At this point, everything is in one list, which means that the
             * remaining probabilities should all be 1/n.  Based on this, set them
             * appropriately.  Due to numerical issues, we can't be sure which
             * stack will hold the entries, so we empty both.             */
            while (small.Count > 0)
                _probability[small.Pop()] = 1.0;            while (large.Count > 0)
                _probability[large.Pop()] = 1.0;
        }        /**
         * Samples a value from the underlying distribution.
         *
         * @return A random value sampled from the underlying distribution.         */
        public int next() {            long tick = DateTime.Now.Ticks;            var seed = ((int)(tick & 0xffffffffL) | (int)(tick >> 32));            unchecked {
                seed = (seed + Guid.NewGuid().GetHashCode() + new Random().Next(0, 100));
            }            var random = new Random(seed);            int column = random.Next(_probability.Length);            /* Generate a biased coin toss to determine which option to pick. */
            bool coinToss = random.NextDouble() < _probability[column];            return coinToss ? column : _alias[column];
        }
    }

测试

Dictionary<String, Double> map = new Dictionary<String, Double>();            map.Add("1金币", 0.2);            map.Add("2金币", 0.15);            map.Add("3金币", 0.1);            map.Add("4金币", 0.05);            map.Add("未中奖", 0.5);            List<Double> list = new List<Double>(map.Values);            List<String> gifts = new List<String>(map.Keys);            AliasMethod method = new AliasMethod(list);            Dictionary<String, int> resultMap = new Dictionary<String, int>();            for (int i = 0; i < 10; i++) {                int index = method.next();                string key = gifts[index];                Console.WriteLine(index+":"+key);            }


发布手记

热门词条