Random draw, but with different odds

Asked

Viewed 6,108 times

15

I am implementing a system where the user clicks on a button and a draw with balls of different colors occurs, but for each color there is a probability:

He has a 30% chance of catching a blue ball He has a 10% chance of catching a red ball It has 5% chance of catching a golden ball He has a 30% chance of catching a black ball It has a 25% chance of catching a gray ball

How to do this draw? I have to create a list where the amount of items represents these odds and then do a random draw or is there a better way?

2 answers

19


As explained by @ramaral, you divide the percentage into proportional ranges.

  • The first 30% is obviously a blue ball.

  • To know if it is a red, the logic is to be greater than 30, and less than or equal to 30 + 10 (which is the percentage of red).

  • To know if it is a gilt, we apply the same reasoning: the value must be greater than 30 of the blue, added to 10 of the red, and less than 30 + 10 + 5 (that is the percentage of the gilded)

  • successively we apply the same logic.

In summary, the range of each color for a logical test is given by the formula

    x > (soma dos ítens anteriores)
    &&
    x <= (soma dos itens anteriores + porcentagem da cor atual)

(see table in @ramaral post for comparison)


Visualizing in another way:

They’re all multiples of five, so let’s make it simple, just for viewing purposes:

 30 / 5 =  6  azul
 10 / 5 =  2  vermelha
  5 / 5 =  1  dourada 
 30 / 5 =  6  preta
 25 / 5 =  5  cinza
100 / 5 = 20  TOTAL

Generic code, just to visualize that we have a ratio of cases according to each percentage:

x = random( 1, 20 )

switch x
   case 1:
   case 2:
   case 3:
   case 4:
   case 5:
   case 6:
      return "azul"
      exit
   case 7:
   case 8:
      return "vermelha"
      exit
   case 9:
      return "dourada"
      exit
   case 10:
   case 11:
   case 12:
   case 13:
   case 14:
   case 15:
      return "preta"
      exit
   case 16: // podia ser um otherwise, claro
   case 17:
   case 18:
   case 19:
   case 20:
      return "cinza"
      exit


Using an algorithm

If you had the need to reuse code in other distributions, it would be the case to make an array of weights, and determine where the result "falls":

lista = {
   30 => 'azul',
   10 => 'vermelha',
    5 => 'dourada',
   30 => 'preta',
   25 => 'cinza'
}

x = random( 1, 100 )

for each item in lista
   x = x - item.key
   if x <= 0
      return item.valor
   endif
next
  • The weight array looks like one of the best ideas so far, as the code gets cleaner and the probabilities of each item are clearly exposed. Can be modified in the future if necessary, making it possible to change the probabilities and add new items faster.

  • 1

    Maybe you can even dry it up depending on the language. But don’t just stick to that solution, there are different ways to do it, which is best only depends on the specific case. Even, if you want to leave really portable, you need to add the keys instead of using the number 100 literally. So you could simply have a 3 => a 1 => b if it was a "three to one" ratio. It doesn’t even depend on a percentage anymore. It works on any scale.

15

Generate a random number x : x [1,100].

  • If x [ 1,30] - caught a blue ball
  • if x [31.40] - caught a red ball
  • if x [41.45] - caught a golden ball
  • if x [46.75] - caught a black ball
  • if x [76,100] - caught a gray ball

Example of implementation in C#.

The class Ballsbag simulates the drawing of colored balls from a bag.
Simulates two behaviors due to whether or not the ball is removed back in the bag.

For each set of balls inserted in the bag(InsertBallsByColor()) a BallSet which keeps the colour and an interval(intervalLeft, intervalRight).
This interval is calculated according to the number of balls already placed and the number of balls in this set.

private int IntervalLeft() => _ballsInBag + 1;
private int IntervalRight(int count) => _ballsInBag + count;

It is used to determine whether, according to the random value generated, a ball of this color has been taken.

public bool WasPicked(int pick)
{
    return pick >= _intervalLeft && pick <= _intervalRight;
}

The probability of a ball coming out of a given color is the relationship between the number of balls of that color in the bag and the total amount of balls in the bag.

public class BallsBag
{
    private static readonly int NUM_MAX_TIRAGENS = 5000;
    private readonly bool _extractedBallReturnsToBag;
    private int _ballsIn;
    private readonly IEnumerator<int>_randomGenerator ;
    private readonly HashSet<BallSet> _ballSetsInBag;
    private int _ballsExtracted;

    public BallsBag(int totalBalls, bool extractedBallReturnsToBag)
    {
        _extractedBallReturnsToBag = extractedBallReturnsToBag;
        TotalBalls = totalBalls;
        _ballSetsInBag = new HashSet<BallSet>();
        _randomGenerator = getRandomGenerator(TotalBalls, extractedBallReturnsToBag);
    }

    public int TotalBalls { get; }

    public int BallsInBag => _ballsIn - _ballsExtracted;

    public void InsertBallsByColor(string color, int count)
    {
        if (count <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(count), $"{count} não é uma quantidade válida de bolas");
        }
        if (BallsExceedsMaximum(count))
        {
            throw new ArgumentOutOfRangeException(nameof(count), "Nº total de bolas excedido");
        }
        if(BagHaveThisBallColor(color))
        {
            throw new ArgumentOutOfRangeException(nameof(color), "O saco já tem bolas dessa cor");
        }

        _ballSetsInBag.Add(new BallSet(color, IntervalLeft, IntervalRight(count)));
        _ballsIn = _ballsIn + count;
    }

    public string ExtractBall()
    {
        if (AllBallsNotInserted)
        {
            throw new InvalidOperationException("Ainda não colocou todas a bolas no saco");
        }
        if (_randomGenerator.MoveNext())
        {
            _ballsExtracted = _ballsExtracted + (_extractedBallReturnsToBag ? 0 : 1);
            var pickedBall = _randomGenerator.Current;
            return _ballSetsInBag.First(ball => ball.WasPicked(pickedBall)).Color;
        }
        throw new InvalidOperationException("O saco está vazio");
    }

    private bool BagHaveThisBallColor(string color) => _ballSetsInBag.Any(ball => ball.Color.Equals(color));
    private bool BallsExceedsMaximum(int count) => _ballsIn + count > TotalBalls;
    private int IntervalLeft => _ballsIn + 1;
    private int IntervalRight(int count) => _ballsIn + count;
    private bool AllBallsNotInserted => _ballsIn < TotalBalls;


    private IEnumerator<int> getRandomGenerator(int totalBalls, bool extractedBallReturnsToBag)
    {
        return extractedBallReturnsToBag ? RandomGenerator(1, totalBalls).GetEnumerator()
                                         : RandomGenerator(1, totalBalls).Distinct()
                                                                         .Take(totalBalls)
                                                                         .GetEnumerator();
    }

    private static IEnumerable<int> RandomGenerator(int minInclued, int maxInclued)
    {
        var rand = new Random();
        var i = 1;
        while (i <= NUM_MAX_TIRAGENS)
        {
            yield return rand.Next(minInclued, maxInclued + 1);
            i++;
        }
    }

    private class BallSet 
    {
        public string Color { get; }
        private readonly int _intervalLeft;
        private readonly int _intervalRight;

        public BallSet(string color, int intervalLeft, int intervalRight)
        {
            Color = color;
            _intervalLeft = intervalLeft;
            _intervalRight = intervalRight;
        }

        public bool WasPicked(int pick)
        {
            return pick >= _intervalLeft && pick <= _intervalRight;
        }

        public override bool Equals(object obj)
        {
            var ballSetObj = obj as BallSet;
            return ballSetObj != null && Color.Equals(ballSetObj.Color);
        }

        public override int GetHashCode()
        {
            return Color.GetHashCode();
        }
    }
}

Example of use:

private static void Main(string[] args)
{
    var ballsBag = new BallsBag(20, extractedBallReturnsToBag: false);

    ballsBag.InsertBallsByColor("Azul",6);
    ballsBag.InsertBallsByColor("Vermelha", 2);
    ballsBag.InsertBallsByColor("Dourada", 1);
    ballsBag.InsertBallsByColor("Preta",6);
    ballsBag.InsertBallsByColor("Cinza", 5);

    Console.WriteLine($"Balls in bag {ballsBag.BallsInBag}");

    for (var i = 0; i < ballsBag.TotalBalls; i++)
    {
        Console.WriteLine($"Tiragem {i+1} - {ballsBag.ExtractBall()} - Balls in bag {ballsBag.BallsInBag}");
    }
    Console.ReadKey();
}

Browser other questions tagged

You are not signed in. Login or sign up in order to post.