c#中獎演算法的實現

演算法名稱 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);
            }

最後推薦個站，全世界的手機號碼免費使用 天神號碼www.ahjesus.com