Control the probability of random winning [C | random]

Preface

      About this algorithm maybe ( sure ) Has been invented , But I 、 My friends around me didn't know and couldn't think of it before , If you don't know , Then it also includes you : ) It should be regarded as “ The invention ” Of ！！ increase 、 Reduce the chance of random draw —— My good friend came up with an algorithm three years ago , I now take it out and carry it forward . This algorithm can be used for Question bank Random questions 、 Gambling machine Control the success rate , even to the extent that tetris Such games , It has a wide range of uses ！ I hope I can help you ！

 

emphasize

      Increase the probability of controlling the winning on the basis of randomness , Pay attention to randomness ！！

 

Text

      One 、 Text explanation ：

           Add a weight to each item of the set to be randomly selected , This weight is random probability , For example, the normal probability of being positive is 1, Then set the weight of the item that you want to be selected with a greater probability to 3 or 5, Then randomly select the items in the set , And multiply the random number by the corresponding weight of each item , Then sort ！！ Before extraction N Just one item ！ You can find that the higher the weight, the higher the probability of being multiplied, and being selected , If the weight is set to 0 Will never be drawn ！

      Two 、 Application scenarios ：

          1.      Random questions ： If question A I passed the exam last year , Then I hope it will appear less or not this year , Then I will ask A The weight of is set to 0, This question will never be selected randomly in the future exam ; And another question B It is a topic in this year's mock examination in our college , I will increase the weight of this problem to 5, According to the algorithm , Then this topic is next time The success rate of random questions It will be several times higher than ordinary questions ！

          2.      Gambling machine ： As we all know, the gambling machine in the game hall can be adjusted , After being transferred, the brilliance rate increased or decreased significantly , I think this algorithm is suitable for explaining . Suppose the gambling machine has 24 There are gambling items to choose from , Namely A-Z Each letter , According to the normal probability, the weight of each item is 1, The dispatcher can improve or reduce the winning rate by dynamically changing the weight . If you put three coins , Choose A、B、C, The gambling machine changes dynamically according to the settings of the adjuster A、B、C A weight , Turn the light 3-4 After the circle, there is a greater chance to stay in the one with less prize money among the three choices .

          3.      tetris ： Everyone is fighting QQ When playing Tetris , Sometimes it's obvious that the higher the pile , What comes out is not satisfactory , I think this algorithm can also achieve this effect . The computer can figure out whether the next best solution is to make a breakthrough or to make a corner , So we can achieve this goal by adjusting the weight to break the average probability of occurrence ！

          ......

      3、 ... and 、 Code implementation （C# Realization ）：

      RandomController.cs

//========================================================================
//                                                                                                                   
//  do   person ： Xiaotang
//  Post   box ：[email protected]
//  Bo   customer ：http://over140.cnblogs.com/
//  when   between ：2009-2-10
//  Sketch   Statement ： Control the probability of random draw .
//                                                                                                                     
//========================================================================

using System;
using System.Collections.Generic;

public class RandomController
{

    #region Member Variables

    // Data set to be randomly extracted
    public List<char> datas = new List<char>(
        new char[]{
            'A','B','C','D','E','F',
            'G','H','I','J','K','L',
            'M','N','O','P','Q','R',
            'S','T','U','V','W','X',
            'Y','Z'
    });

    // A weight
    public List<ushort> weights = new List<ushort>(
        new ushort[]{
            1,2,3,4,5,6,
            7,8,9,0,1,1,
            1,1,1,1,1,1,
            1,1,1,1,1,1,
            1,1
    });

    #endregion

    #region Contructors

    /// <summary>
    ///  Constructors
    /// </summary>
    /// <param name="count"> Random number </param>
    public RandomController(ushort count)
    {
        if (count > 26)
            throw new Exception(" The number of extracts cannot exceed the size of the data set ！！");

        _Count = count;
    }

    #endregion

    #region Method

    #region  Ordinary random sampling

    /// <summary>
    ///  Random sampling
    /// </summary>
    /// <param name="rand"> Random number generator </param>
    /// <returns></returns>
    public char[] RandomExtract(Random rand)
    {
        List<char> result = new List<char>();
        if (rand != null)
        {
            for (int i = Count; i > 0; )
            {
                char item = datas[rand.Next(25)];
                if (result.Contains(item))
                    continue;
                else
                {
                    result.Add(item);
                    i--;
                }
            }
        }
        return result.ToArray();
    }

    #endregion

    #region  Controlled random sampling

    /// <summary>
    ///  Random sampling
    /// </summary>
    /// <param name="rand"> Random number generator </param>
    /// <returns></returns>
    public char[] ControllerRandomExtract(Random rand)
    {
        List<char> result = new List<char>();
        if (rand != null)
        {
            // Temporary variable
            Dictionary<char, int> dict = new Dictionary<char, int>(26);

            // Calculate a random number for each term and multiply it by the corresponding weight
            for (int i = datas.Count - 1; i >= 0; i--)
            {
                dict.Add(datas[i], rand.Next(100) * weights[i]);
            }

            // Sort
            List<KeyValuePair<char, int>> listDict = SortByValue(dict);

            // The top with the largest weight of copy extraction Count term
            foreach (KeyValuePair<char, int> kvp in listDict.GetRange(0, Count))
            {
                result.Add(kvp.Key);
            }
        }
        return result.ToArray();
    }

    #endregion

    #region Tools

    /// <summary>
    ///  Sort set
    /// </summary>
    /// <param name="dict"></param>
    /// <returns></returns>
    private List<KeyValuePair<char, int>> SortByValue(Dictionary<char, int> dict)
    {
        List<KeyValuePair<char, int>> list = new List<KeyValuePair<char, int>>();

        if (dict != null)
        {
            list.AddRange(dict);

            list.Sort(
              delegate(KeyValuePair<char, int> kvp1, KeyValuePair<char, int> kvp2)
              {
                  return kvp2.Value - kvp1.Value;
              });
        }
        return list;
    }


    #endregion

    #endregion

    #region Properties

    private int _Count;
    /// <summary>
    ///  Random number
    /// </summary>
    public int Count
    {
        get
        {
            return _Count;
        }
        set
        {
            _Count = value;
        }
    }

    #endregion
}

----------------------------------------------------------------------------------------

      Call the test code ：

        static void Main(string[] args)
        {
            // Randomly select a number from the set
            const ushort COUNT = 6;
            // cycles
            const int FOR_COUNT = 1000;//10000

            #region 1000、10000 Random sampling , Every time I draw 6 individual

            RandomController rc = new RandomController(COUNT);
            // Accumulator
            Dictionary<char, int> result = new Dictionary<char, int>();
            // Random number generator
            Random rand = new Random();
            // Loop generates random numbers
            for (int i = 0; i < FOR_COUNT; i++)
            {
                char[] rands = rc.RandomExtract(rand);
                for (int j = 0; j < COUNT; j++)
                {
                    char item = rands[j];
                    if (result.ContainsKey(item))
                        result[item] += 1;
                    else
                        result.Add(item, 1);
                }
                Thread.Sleep(5);
            }

            Console.WriteLine("\t\t Number of occurrences \t Percentage of total occurrences ");

            foreach (KeyValuePair<char, int> item in result)
            {
                Console.WriteLine(item.Key + "\t\t" + item.Value.ToString() + "\t\t" + ((double)item.Value / (double)(FOR_COUNT * COUNT)).ToString("0.00%"));
            }
        }

 

      Ordinary random sampling is carried out separately 1000 Secondary sum 10000 This test shows ：

          1000 Time

          

          10000 Time

          

      Control the random probability and random sampling respectively 1000 Secondary sum 10000 This code modification ：

          1.      take rc.RandomExtract(rand) Change it to rc.ControllerRandomExtract(rand)

          2.      Comment out the output part of the code above , Add the following code ：

            Dictionary<char,ushort> items = new Dictionary<char,ushort>();
            for (int i = 0,j = rc.datas.Count; i < j; i++)
            {
                items.Add(rc.datas[i],rc.weights[i]);
            }

            Console.WriteLine("\t\t Number of occurrences \t Percentage of total occurrences \t A weight ");
            
            foreach (KeyValuePair<char, int> item in result)
            {
                Console.WriteLine(item.Key + "\t\t" + item.Value.ToString() + "\t\t" + ((double)item.Value / (double)(FOR_COUNT * COUNT)).ToString("0.00%") + "\t\t\t" + items[item.Key]);
            }

           test result ：

          1000 Time

          

          10000 Time

          

 

Summary

      From the above statistical results, we can see , Ordinary random numbers are evenly distributed , The probability of random drawing is relatively flat ; But after controlling the probability of random selection , Those with high weight have a higher chance of striking , Another thing to note is that only 25 Letters , That is, there is another letter that has not been selected , Because according to the algorithm, he will never appear , Unless you smoke once 26 individual ！！

      It should be noted that ：

          1.      Reasonable allocation of weights is also related to the size of random number generation , You can see the weight 5 And weight 1 The difference in the probability of occurrence is not 5 times , It is 30-50 times .

          2.      If the random data of the data source is large , For example, thousands of , According to the current procedure, it is not feasible , You can draw more randomly than you need 2-5 Times the data , Then sort directly by weight, and then extract the front N Bit to achieve the goal .

          3.      The most important point is to pay attention to randomness , This algorithm is worthless if it is not based on random mechanism ！！

     

end

      When you lose the chance to invent , We can consider better application of it ！！